[프로그래머스] 숫자블록 파이썬 풀이

숫자블록 (Lv.2)

구현 요구사항

1. 처음에 0으로 초기화된 숫자 블록이 주어진다.
2. 블록의 번호가 n일 때, n이 아닌, n의 배수인 블럭들에 n블럭을 설치한다.
3. 예) 1번 블록은 2, 3, 4, 5,... 블럭에, 2번 블록은 4, 6, 8, 10, ...
4. 길이가 1,000,000,000인 도로에 1번 블록부터 시작하여 10,000,000번 블록까지 위의 규칙으로 모두 놓았습니다.

4번이 중요하다.

입출력 예시는 아래 그림과 같다.

구현 방법

• 처음에 형태를 보고 에라토스테네스의 체가 떠올랐지만 문제에서 물어보는 것은 더 간단하다.

• 각 n 숫자 블럭에서, n의 약수 중 최대 약수를 구하면 된다.

• 약수를 구하는 것은 좀 익숙한 문제다. 2~sqrt(n)까지 순회하며 n과 나누어 떨어지는 수가 그 약수다.

숫자 블럭의 최대 값과 도로 길이의 최대 값이 다른 것에 유의하여 풀어야 한다.
숫자 블럭의 최대 값은 10,000,000 이지만 도로 길이는 최대 1,000,000,000가 될 수 있다.

코드

def solution(begin, end):
    answer = []
    for i in range(begin, end+1):
        k = int(i != 1)  # i가 1이면 0, 1이 아니면 1을 대입
        for j in range(2, int(i**0.5)+1): # i**0.5 == sqrt(i)
            if i%j == 0 and i//j <= 10000000:
                k = i//j  # j가 2부터 커지기 때문에 처음 만나는 i//j가 약수 중 가장 큰 값
                break
        answer.append(k)
    
    return answer