문제는 오름차순으로 정렬된 소수로 이뤄진 리스트가 주어졌을 때, 2개의 원소를 뽑아 더 큰 수를 분모로, 더 작은 수를 분자로 한 값을 기반으로 k번째로 작은 수를 형성하는 2개의 원소를 return 하는 문제이다. 나는 구현 문제로 취급하여 간단히 해결하였으나 binary search를 활용해 시간 복잡도를 개선할 수 있는 문제였다.
itertools의 combinations를 활용해 2개의 모든 조합 가능한 경우의 수를 도출한다. ⇒ 원소를 2개만 뽑아서 값을 만드는 문제이기 때문에 itertools를 사용하지 않고 이중 for문을 사용하는게 나을 듯 하다.
해당 set을 순회하며, small/big 값과 이 값을 구성하는 2개의 원소를 묶어서 list에 넣는다.
list를 정렬한다. ⇒ 아예 처음부터 heapq를 활용했으면, 이 과정없이 push를 넣는 순간 정렬이 되므로 이를 사용하는게 나은 듯 하다.
k번째 값을 조회한다.
https://leetcode.com/problems/k-th-smallest-prime-fraction/solutions/5137467/fastest-100-easy-clean-concise-multiple-approaches/
a. We start with a range of possible values, from 0 to 1 in this case.
b. We pick a value in the middle of the range, let's call it "mid."
c. Then, we count how many fractions are less than or equal to "mid."
d. If the count is equal to k, we've found our kth smallest fraction! Woohoo!
e. If the count is less than k, we need to search for a larger fraction, so we update the lower bound of our range to "mid."