문제 설명
두 개의 양수 n과 k가 주어집니다. n의 모든 약수를 오름차순으로 정렬한 목록에서 k번째 약수를 찾아야 하며, 만약 n의 약수 개수가 k보다 적다면 -1을 반환해야 합니다.
예를 들어 n = 28, k = 4라고 가정해 보겠습니다. 28의 약수는 [1, 2, 4, 7, 14, 28]이고, 이 중 네 번째 약수는 7이므로 결과값은 7이 됩니다.
접근 방법
모든 수를 일일이 확인하는 대신, 제곱근까지만 탐색하면 효율적으로 문제를 해결할 수 있습니다. 약수는 항상 쌍(pair)으로 존재하기 때문입니다. 즉, i가 n의 약수라면 n/i 역시 n의 약수입니다. 이 대칭성을 활용한 해결 단계는 다음과 같습니다.
- 1단계: k가 1이면 첫 번째 약수는 항상 1이므로 즉시 1을 반환합니다.
- 2단계: 후보 약수를 저장할 리스트 cand를 [1]로 초기화합니다.
- 3단계: i를 2부터 √n의 내림값까지 반복하면서, n을 i로 나눈 나머지가 0이면 i를 cand에 추가합니다.
- 4단계: 반복이 끝나면 cand의 크기를 m이라고 합니다. 이때 전체 약수의 개수는 최대 2m개입니다(n이 완전제곱수이면 2m-1개).
- 5단계: k가 2m보다 크거나, k가 2m과 같으면서 n이 완전제곱수(cand의 마지막 원소의 제곱)라면 약수가 부족하므로 -1을 반환합니다.
- 6단계: k가 m 이하라면 작은 약수 영역에 해당하므로 cand[k-1]을 그대로 반환합니다.
- 7단계: k가 m보다 크다면 큰 약수 영역에 해당합니다. factor를 cand[2m-k]로 설정하고, n을 factor로 나눈 몫을 반환합니다.
핵심 아이디어는 약수의 대칭성입니다. 오름차순으로 정렬된 약수 목록에서 뒤쪽의 큰 약수는 'n ÷ 앞쪽의 작은 약수'와 같습니다. 따라서 k번째 약수가 큰 약수 영역에 있다면, 대응되는 작은 약수로 n을 나누어 답을 구할 수 있습니다.
Python 구현 예제
from math import floor
def solve(n, k):
if k == 1:
return 1
cand = [1]
for i in range(2, 1 + floor(pow(n, 0.5))):
if n % i == 0:
cand.append(i)
m = len(cand)
if k > 2 * m or (k == 2 * m and n == cand[-1] ** 2):
return -1
if k <= m:
return cand[k - 1]
factor = cand[2 * m - k]
return n // factor
n = 28
k = 4
print(solve(n, k))
입력
28, 4
출력
7
복잡도 분석
- 시간 복잡도: O(√n) — √n까지만 반복문을 수행하므로 매우 효율적입니다.
- 공간 복잡도: O(√n) — √n 이하의 작은 약수를 저장하는 리스트가 필요합니다.