[구현] (2-1) 약수 구할때에 시간복잡도 줄이기

문제

어떤 자연수 p와 q가 있을 때, 만일 p를 q로 나누었을 때 나머지가 0이면 q는 p의 약수이다. 6을 예로 들면

6÷1=6...0 6÷2=3...0 6÷3=2...0 6÷4=1...2 6÷5=1...1 6÷6=1...0

그래서 6의 약수는 1, 2, 3, 6, 총 네 개이다.
두 개의 자연수 N과 K가 주어졌을 때, N의 약수들 중 K번째로 작은 수를 출력하는 프로그램을 작성하시오.

<입력설명>
첫째 줄에 N과 K가 빈칸을 사이에 두고 주어진다. N은 1 이상 10,000 이하이다. K는 1 이상 N 이하이다.

<출력설명>
첫째 줄에 N의 약수들 중 K번째로 작은 수를 출력한다. 만일 N의 약수의 개수가 K개보다 적어서 K번째 약수가 존재하지 않을 경우에는 -1을 출력하시오.

입력예제

1 63

출력예제

1 3

 

위 문제의 constraint의 경우 10,000 이하에서의 약수를 구하기 때문에, 어떻게 코드를 작성해도 시간초과에 자유롭겠지만,

만약 100,000,000,000의 수의 약수를 구할경우, for문으로 1~N까지를 다 나눠보는 코드는 시간초과 될 것이다.

 

여기에서 중학교 수학에서의 영감을 가져온다.

 

예를 들어 24의 약수를 생각해보면

1, 2, 3, 4, 6, 8, 12, 24이다. 

너무나 당연하지만, 가운데를 중심으로 두개의 약수는 대칭성을 가진다. (1*24 = 2*12 = 3*8 = 4*6)

즉, 1~6까지만 N으로 나누고, 그 대칭약수를 따로구하면,

24번 연산할 것을 6*2 = 12번의 연산으로 끝이 난다.

 

그렇다면 '중심'은 어떤 숫자인가?를 알아봐야하는데,

144를 예로 들어보자.

 

1, 2, 3, 4, 6, 8, 9, 12,    16, 18, 24, 48, 72, 144 이다.

144의 경우 제곱수 (12^2)이기 때문에 중심이 12라는 integer값으로 명확하다.

 

그렇다면, 제곱수가 아닌 숫자의 경우 sqrt(N)까지만 for문으로 계산해 보면 되기 때문에, for문을 int(sqrt(N))까지 계산하면 될것이다.

 

그렇다면 시간복잡도는 sqrt(N)*2 가 된다. 큰 숫자 일수록 효율적인 방법이 될 것이다.

import sys
from math import sqrt
input = sys.stdin.readline

N, K = map(int, input().split())
# print(N, K)

def find (N, K):
    yak_list = []
    cnt_k = 0

    for i in range(1, int(sqrt(N))+2):
        if N%i == 0:
            yak_list.append(i)
            cnt_k += 1
        if cnt_k == K: return(print(yak_list.pop()))
    for left_yak in sorted(yak_list, reverse=True):
        if int(N/left_yak) == left_yak:
            continue
        yak_list.append(int(N/left_yak))
        cnt_k += 1
        if cnt_k == K: return(print(yak_list.pop()))

    return print(-1)
find(N, K)

 

 위 문제는 약수를 찾고, 각 약수의 order가 중요한 문제.

 

그렇기 때문에 대칭약수를 찾을때에, 순서대로 정확하게 list에 들어가게 하기 위해서(yak_list)

sorted(reverse = True)를 사용하였다.

하지만 이는 그렇게 효율적인 방법은 또 아니다.

sort하는데에 O( sqrt(N)ln(sqrt(N)) ) 를 가지기 때문이지.

 

이에 대한 발전된 방법은 추후 약수 및 소수문제를 풀때에 다시 언급하겠다.