Lv4. 숫자 블록

# 문제 설명

그렙시에는 0으로 된 도로에 숫자 블록을 설치하기로 하였습니다. 숫자 블록의 규칙은 다음과 같습니다.

블록의 번호가 n 일 때, 가장 처음 블록은 n * 2번째 위치에 설치합니다. 그다음은 n * 3, 그다음은 n * 4, …로 진행합니다.만약 기존에 블록이 깔려있는 자리라면 그 블록을빼고 새로운 블록으로 집어넣습니다.

예를 들어 1번 블록은 2,3,4,5, … 인 위치에 우선 설치합니다. 그다음 2번 블록은 4,6,8,10, … 인 위치에 설치하고, 3번 블록은 6,9,12… 인 위치에 설치합니다.

이렇게 3번 블록까지 설치하고 나면 첫 10개의 블록은 0, 1, 1, 2, 1, 3, 1, 2, 3, 2이됩니다.

그렙시는 길이가 1,000,000,000인 도로에 1번 블록부터 시작하여 10,000,000번 블록까지 위의 규칙으로 모두 놓았습니다.

그렙시의 시장님은 특정 구간의 어떤 블록이 깔려 있는지 알고 싶습니다.

구간을 나타내는 두 수 begin, end 가 매개변수로 주어 질 때, 그 구간에 깔려 있는 블록의 숫자 배열(리스트)을 return하는 solution 함수를 완성해 주세요.

# 제한 사항

• begin, end 는 1 이상 1,000,000,000이하의 자연수 이고, begin는 항상 end보다 작습니다.
• end - begin 의 값은 항상 10,000을 넘지 않습니다.

# 입출력 예

• 입출력 예 설명

  입출력 예 #1 다음과 같이 블럭이 깔리게 됩니다.

문제 해결 시 고려사항

• 에라토스테네스의 체 활용

본 문제를 풀이하기 위한 아이디어로 필자는 에라토스테네스의 체를 활용하였다.

에라토스테네스는 원래 소수를 찾아내는 알고리즘이지만 본 문제에서 요구하는 사항 또한 유사하였다. 해당 유사점은 n번 블록을 n x 2위치에 설치한다는 점이다. 따라서, n번 블록을 소수값에 n x 2위치에 우선적으로 설치해나가면 되는 것이다.

같은 시간에 여러 작업을 처리할 수 있다면 가능한 작업 중 작업 시간이 가장 짧은 작업을 우선적으로 처리하여 주면 자연적으로, 평균 소요 시간의 최소화가 가능하다.

따라서, 필자는 처리해야할 작업을 리스트에 담고 이를 heapify하여 최소 작업 시간을 가진 작업을 우선적으로 처리하도록 하여 모든 프로세스를 끝내는 시점에 평균 소요시간을 반환하도록 하였다.

 for i in range(begin, end+1):
         # 1 위치에는 0블록(default: 0블록)
         if i < 2:
             result.append(0)
         # 그 이외의 위치에는 n번 블록은 n*2 위치에
         # (ex)1번 블록은 2,3,4,5....
         else:
             #2부터 i의 제곱근까지 최초로 나누어 떨어지는 값 검사 후 해당 값 블록 추가
             for j in range(2, int(math.sqrt(i))+1):
                 # 10,000,000번 블록까지만 존재하기 때문에 해당 정보도 검사
                 if i % j == 0 and i // j <= 10000000:
                     result.append(i // j)
                     break
             else:
                 # 2번 위치부터의 default는 1번 블록
                 result.append(1)

기본적으로 도로에는 0번 블록이 설치되어 있고, 1번 블록은 2,3,4,5,6…, 2번 블록은 4,6,8,10…. 이러한 패턴으로 설치 되기 때문에 begin부터 end까지의 구간 내에서 반복문을 실행하여 2부터 i의 제곱근 중 최초로 나누어 떨어지는 값을 통해 해당 몫을 append해주면 해당 구간의 블록 설치 패턴을 구할 수 있는 것이다.

전체 코드

import math
def solution(begin, end):
    result = []
    for i in range(begin, end+1):
        # 1 위치에는 0블록(default: 0블록)
        if i < 2:
            result.append(0)
        # 그 이외의 위치에는 n번 블록은 n*2 위치에
        # (ex)1번 블록은 2,3,4,5....
        else:
            #2부터 i의 제곱근까지 최초로 나누어 떨어지는 값 검사 후 해당 값 블록 추가
            for j in range(2, int(math.sqrt(i))+1):
                # 10,000,000번 블록까지만 존재하기 때문에 해당 정보도 검사
                if i % j == 0 and i // j <= 10000000:
                    result.append(i // j)
                    break
            else:
                # 2번 위치부터의 default는 1번 블록
                result.append(1)
    return result