(Python/LV2) 숫자 블록

문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/12923

프로그래머스

풀이

첫 도전

def solution(begin, end):
    lists = [0 for i in range(0, begin+1)]
    lists.extend([0] * (end-begin))

    for i in range(begin, end//2 + 1):
        for j in list(range(i, end+1, i)):
            if j == i:
                continue
            else:
                lists[j] = i

    return lists[begin:]
  
  테스트 케이스만 맞고 다 틀림

2번째.

def solution (begin, end):
    list = []
    for i in range(begin, end+1):
        if i == 1:
            list.append(0)
        elif 1 == 2:
            list.append(1)
        else:
            gong = []
            for j in range(1,i+1):
                if i % j == 0:
                    gong.append(j)
            if len(gong) == 2:
                list.append(1)
            else:
                list.append(gong[-2])
    return list

정확성은 100 효율성은 시간초과 이중포문 이라 그런가보다

3번째

def solution (begin, end):
    list = []
    for i in range(begin, end+1):
        if i == 1:
            list.append(0)
        elif 1 == 2:
            list.append(1)
        else:
            gong = []
            for j in range(1,int((i+1)**0.5) + 1):
                if i % j == 0:
                    gong.append(i // j)
            if len(gong) == 1:
                list.append(1)
            else:
                list.append(gong[1])
    return list

이중포문에서 두번째 포문을 제곱근을 사용해서 했지만 시간초과는 나오지 않지만 틀린다.

 

 

4번째 최종 + 정리

def solution (begin, end):
    list = []
    for i in range(begin, end+1):
        if i < 2:
            list.append(0)
        else:
            for j in range(2,int((i+1)**0.5) + 1):
                if i % j == 0 and i // j <= 10000000:
                    list.append(i // j)
                    break
            else:
                list.append(1)
    return list

i < 2 보다 작은경우 무조건 0을 대입해준다

else

2부터 해당 숫자의 제곱근까지 포문을 돌려서

해당 숫자를 2부터 나눠서 나누어 떨어졌을때 >> 가장큰값    Ex) 8이면 1,2,4,8 인데 2로 나눴을때 4로 4를 넣어줘야하는 느낌

첫 값을 넣어주고 break 를 해줘야함 안 해주면 1,2,4,8 다 들어간다

 

그리고 문제에 10,000,000번 블록까지 위의 규칙 이라 써있다.

 

>> i // j 가 10 000 000 보다 작아야 한다는 뜻

 

그외 나머지 7이나 11같은 소수면 그냥 1  넣기