숫자 블록(프로그래머스) 문제풀이

문제 

https://school.programmers.co.kr/learn/courses/30/lessons/12923

프로그래머스

 

 

문제 접근 방식

블록의 숫자를 높여가면서 곱했을 때의 해당하는 도로에 해당 블록을 계속해서 바꿔줘야한다. 규칙을 보면 약수와 관련이 있다는 것을 알 수 있으며 최종적으로 블록에 들어가는 숫자는 해당 도로 번호의 약수 중 자신을 제외한 최대 약수 값이 된다. 예를 들어, 16번 도로의 경우, 약수 [1, 2, 4, 8, 16] 중 자신을 제외한 최대 약수인 8이 최종 블록이 됨을 알 수 있다.

 

에러

이렇게 해서 풀었는데 테스트 케이스에서 에러가 발생했고, 해당 예외를 찾지 못해 다른 분의 코드를 참고해서 해결을 했다. 문제가 발생하는 부분은 아래와 같다.

블록의 최대 번호는 1e7 인데, 로직의 경우 최소 약수를 시작으로 나눠서 배열에 넣기 때문에 
1e7 초과인 번호가 들어가는 경우가 생긴다

ex. 1e8번 도로에 대해 처리할 때, 2로 나눈 몫인 5e7이 블록 값으로 저장된다. 이는 블록 범위를 초과한다

 

이러한 경우를 위해 아래와 같은 코드로 오버플로우가 발생했을 때의 처리를 해줘야한다.

 

MAX=int(1e7)
for i in range(begin,end+1):
    for j in range(2,int(sqrt(i))+1):
        if i%j==0 and i//j <= MAX:
            nums[i-begin]=i//j
            break
        elif i%j==0 and i//j>MAX: ## 오버플로우 처리, 가장 최근에 나누는 약수를 값으로 정해준다(break 문이 없다는 점 참고)
            nums[i-begin]=j

 

시간 복잡도

외부 for문에서 최대 5e3 번을 돌 수 있으며, 내부 for문에서  sqrt(1e9) = 대약 (3e4) 번 정도 for문을 돈다. 그러므로 시간내에 동작함을 알 수 있다.

 

 

코드

from math import sqrt

MAX=int(1e7)
def solution(begin, end):
    nums=[1]*(end-begin+1)
    for i in range(begin,end+1):
        for j in range(2,int(sqrt(i))+1):
            if i%j==0 and i//j <= MAX:
                nums[i-begin]=i//j
                break
            elif i%j==0 and i//j>MAX:
                nums[i-begin]=j
    if begin==1:
        nums[0]=0
        
        
    return nums

 

 

회고

범위에 대해서 신경을 쓰고, 처음, 끝 부분에 유의하여 예외가 발생하는 곳이 있는지를 확인해서 처리해주자