[LeetCode/Python] 1492. The kth Factor of n

n의 약수를 찾고 그 중 k번째 숫자를 리턴하는 문제이다.

간단한 문제였다.

 

class Solution:
    def kthFactor(self, n: int, k: int) -> int:
        divisor = set([])

        for i in range(1, int(n**(1/2)) + 1):
            if (n % i == 0):
                divisor.add(i)
                divisor.add(n // i)
        
        if k > len(divisor):
            return -1

        return sorted(list(divisor))[k-1]

 

시간 복잡도

약수를 구할 숫자: N

=> O(1/2N)

 

 

다른 사람 풀이

- 전체 배열을 구하지 않고 딱 k번째 일때 리턴하는 풀이... 와우... 그러게 쓸데없이 다 구할 필요는 없었다!

class Solution(object):
    def kthFactor(self, n, k):
        count = 0
        for i in range(1,n+1):
            if n % i == 0 :
                count+=1
                if count == k: return i
        return -1