프로그래머스: 숫자블록 (파이썬, 구현)

프로그래머스에는 약수를 구하는 문제가 꽤 많은데 그 중 한 문제이다.

길의 길이는 10^9이고 블록의 길이는 최대 10^7이기에 완전탐색을 하면 틀리는 문제이다.

 

약수를 효율적으로 구하는 것이 문제의 핵심인데 약수는 일일이 나눠서 구해야하므로 완전탐색으로 구해야하고, 더 빠르게 구하려면 약수는 제곱근 전 후로 쌍을 이룬다는 성질을 응용하여 제곱근까지만 약수를 구하고 그 약수들로 수를 나누어 나머지 약수들을 찾아야 한다.

 

먼저 내가 푼 코드이다.

from bisect import bisect_left


def get_yaksu(num):
    # 1은 모든 수의 약수
    yaksu = [1]
    # 제곱근까지 약수를 구함 으로써 탐색 범위를 줄임
    for i in range(2, int(num**0.5)+1):
        if num%i == 0:
            yaksu.append(i)
    return yaksu


def solution(begin, end):
    answer = [0 for _ in range(begin, end+1)]
    for i in range(0, len(answer)):
        # begin과 길의 시작이 서로 달라 둘을 더해서 구간을 맞춤
        division = i + begin
        yaksu = get_yaksu(division)
        # 번호가 n인 블록은 2n부터 설치함으로 약수가 end를 2로 나눈 것보다 클 수 없음
        bound = bisect_left(yaksu, int(end//2)+1)
        # 소수가 아닌 경우와 소수인 경우 나누기
        if 1 < len(yaksu) == bound:
            cash = division // yaksu[1]
            if cash > 10000000:
                # 약수가 10^7보다 크면 제곱근 전 까지의 약수들로 나눈 수 중 10^7보다 작으며 최대인 값 찾기
                k, cash = 0, 1
                while k < len(yaksu) and cash <= 10000000:
                    temp = division // yaksu[k]
                    if cash < temp <= 10000000:
                        cash = temp
                    k += 1
            answer[i] = cash
        else:
            answer[i] = yaksu[bound-1]
    # 구간 맞추는 용으로 넣어둠
    if begin == 1:
        answer[0] = 0
    return answer

다만 문제에 이해가 가지 않는 점이 하나 있는데 효율성 테스트 케이스들이 잘못 된 것 같다. 

 

정확성 테스트는 모두 통과하는데 효율성 테스트는 시간초과가 아닌 실패가 뜬다면 두가지를 짚어봐야 한다.

먼저 문제의 조건에서 블록은 10^7까지만 있다는 점이다. 따라서 최대약수가 10^7보다 크다면 10^7보다 작은 약수들 중 가장 큰 약수를 구하도록 코드를 바꿔야한다.

두번째로는 제곱근보다 작은 약수들로 구한 약수들이 모두 10^7보다 클 수 있다. 그렇다면 최대약수는 제곱근전까지 약수들 중 가장 큰 값이 되어야 할 것 같은데 그렇지 않고 모두 1로 출력해야 답이 맞는다.

 

예를 들면 999999996의 제곱근 전까지의 약수는 [1, 2, 3, 4, 6, 12]이다. 각각의 수들로 999999996를 나누어 구한 약수들은 모두 10^7보다 크다. 그렇다면 최대약수는 12가 되어야 할 것 같은데 그렇게 구하면 틀리고 최대약수가 1이라 하여야 효율성 테스트를 통과하는 것을 볼 수 있었다.