Problem link
https://leetcode.com/problems/the-kth-factor-of-n/
Problem Summary
n의 약수 중 k번째 작은 수를 찾는 문제
Solution
그냥 모든 약수를 구하고 정렬 후 k번째를 찾으면 된다.
Follow up
정렬해도 O(n) 이하긴 한데 (O(sqrt(n) log sqrt(n))) 정렬 없이 풀 수 있다.
약수 저장 배열을 2개 두면 된다.
약수를 구할 때 d가 약수이면 배열에 d를 넣고 다른 배열은 n/d를 집어넣으면 각 배열은 정렬이 되어있는 상태이고 k번째는 한번에 구할 수 있다.
이렇게 되면 시간복잡도는 O(sqrt(n))
배열에 넣지 않고 k를 빼주면서 하면 공간복잡도를 O(1)까지 가능하긴 하다.
Source Code
class Solution:
def kthFactor(self, n: int, k: int) -> int:
smallfactors = []
largefactors = []
i = 1
while i*i <= n:
if n % i == 0:
smallfactors.append(i)
if i != n//i:
largefactors.append(n//i)
i += 1
sl = len(smallfactors)
ll = len(largefactors)
if k > sl + ll:
return -1
if k > sl:
return largefactors[-(k - sl)]
return smallfactors[k - 1]