프로그래머스[ LV2 | Python ] 숫자 블록

문제

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

풀이

주어진 예시 1부터 10까지의 begin이 1이고 end가 10인 경우를 보았을 때, 도로의 각 칸은 자기 자신이 아닌 가장 큰 수로 나누어떨어졌을 때의 몫을 가지는 블럭이나, 도로 칸이 소수인 경우 1인 블럭으로 채워진다.

위의 조건을 미뤄보았을 때 몫을 찾는 과정에서 나누어 떨어지지 않는 수는 소수로 보고 도로의 모든 값을 1로 둔다.

이 때 begin 값이 1이라면 road의 index는 0으로 두어야한다.

이후로 위의 조건에 맞추어 해결하는데, 문제에서는 도로의 길이는$10^9$ 까지 주어진데 반해 블록은 $10^7$까지 주어져 있다.

이를 주의해 몫이 $10^7$인 경우를 피해 답을 낸다.

def solution(begin, end):
    import math

    road = [1]*((end-begin)+1)

    for i in range(end,begin-1,-1):
        r = int(math.sqrt(i))
        for j in range(2,r+1):
            div,mod = divmod(i,j)
            if div > 10**7:
                continue
            if mod == 0:
                road[i-begin] = div
                break

    if begin == 1:
        road[0] = 0
        
    return road

생각 & 정리

정확도 까지는 어렵지 않게 맞출 수 있었는데, $10^7$ 조건으로 인해서 조금 헤맸다.
효율성 테스트에서 시간초과로 떠서 그저 효율성이 떨어지는 줄로만 생각하고 있었는데, 조건에 맞지 않아 몫을 하나하나 구하고 있기 때문이었던 것 같다.

내가 짠 흐름이 맞다고 생각된다면, 조건을 다시 확인해보는 것이 좋을 것 같다.