n의 약수를 오름차순으로 정렬할 때 k번째 원소를 구하라

양의 정수 n과 k가 주어진다.  정수 n의 약수는 n % i == 0을 만족하는 정수 i로 정의된다.
n의 모든 약수를 오름차순으로 정렬한 목록을 고려하여, 이 목록에서 k번째 약수를 반환하거나 n의 약수가 k개 미만인 경우 -1을 반환하세요. 이 문제를 O(n) 복잡도보다 적게 해결하도록 해봅시다 (제한 조건:  1 <= k <= n <= 1000).

이 문제를 풀 때는 [1, 2, 3, 4, 6, 12]와 [1, 2, 4] 같은 것을 보면 해법을 잘 알 수 있다. 예를 들어 입력: n = 12일 때, 약수 목록은 [1, 2, 3, 4, 6, 12]이다. 또 n = 4이면 약수 목록은 [1, 2, 4]이다.

i=1부터 차례로 대입해서 i가 n을 나누어 떨어지는지를 보면 되지만 (즉, O(n)), 예를 들어 n=12인 경우라면 i=3을 넘어가면 (3,4)의 약수의 쌍이 (4,3)으로 바뀔 뿐, 결국 앞에서 했던 일을 반복하게 되기 때문에, 3과 4 사이에 있는 어떤 임계점을 넘어서면 작업을 진행할 필요가 없다는 것을 짐작할 수 있다.

또, n = 4인 경우에는, (2, 2)의 약수의 쌍을 만나게 되는데, 이는 약수가 겹치게 되는 것이다.

결국 n=12라면 1, 2, 3을, n=4라면 1, 2를 약수 후보로서 시도해 보면 되며, 이 두 경우를 모두 만족시키는 식은 floor(sqrt(n)) 가 된다.

import math

def kthFactor(n: int, k: int) -> int:
    factors = []
    for i in range(1, math.floor(math.sqrt(n)) + 1):
        if n % i == 0:
            factors.append(i)
            if i != n//i:
                factors.append(n//i)
    if k > len(factors):
        return -1
    factors.sort()
    return factors[k-1]

 

문제는 여기서 풀어볼 수 있다.

https://leetcode.com/problems/the-kth-factor-of-n/

The kth Factor of n - LeetCode