[leetcode][1492] The kth Factor of n

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

---

양수 n, k가 주어질 때, n으로 나누어 떨어지는 정수들을 오름차순 정렬했을 때, k번째로 나오는 수를 구하라.

---

1부터 루트 n 만큼 반복문을 돌면서 k를 감소시킨다.

만약 n이 탐색 중인 수 i 으로 나누어 떨어졌을 때 배열에 n/i를 저장한다.

탐색 중에 k가 0이 된다면 i가 정답이 된다.

만약 i의 제곱이 n이라면 반복문 중에 k를 한 번 소모하는데 벌써 사용이 되었으므로 배열에 저장하지 않는다.

탐색이 끝났을 때 배열 크기보다 k가 크다면 정답이 없는 경우이므로 -1을 반환한다.

정답이 있는 경우 배열의 뒤에서 k번째에 있는 수가 정답이 된다.

 

시간복잡도는 O(루트n).

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/1492.%20The%20kth%20Factor%20of%20n.cpp