99클럽 코테 스터디 22일차 TIL / k-th-smallest-prime-fraction

k-th-smallest-prime-fraction

학습 키워드: 이분 탐색(binary search), 수학(math)
학습 링크: https://leetcode.com/problems/k-th-smallest-prime-fraction/

문제 설명

제한 조건

문제 풀이

문제는 mid값을 기준으로 어떻게 해당 함수를 구현하는 지에 달려있다. 문제에서 어려움을 겪은 점은 arr[2]/arr[3]과 arr[1]/arr[2] 중 어떤 값이 큰 지 모르기 때문에 크기 비교를 위해 어떻게 코드를 작성해 나가야 하느냐이다. 해당 부분을 진행하기 위해 힌트를 구해서 풀었다.
그 답은 코드를 구현할 때 분자를 기준으로 해서 분모를 for문으로 돌린 뒤 mid값과 비교해 개수를 계속 더해주는 것으로 찾을 수 있다. while문을 돌면서 mid를 기준으로 분모를 늘려주면서 mid보다 작아지는 때를 찾은뒤 cnt에 더해준다.(분자가 같을 때 분모가 커지면 무조건 더 작아지기 때문) 그 후, cnt의 값을 비교해서 클 때 작을 때 구간을 좁혀서 비교해주고 같을 때 break를 걸어서 탈출한 뒤 index i,j번째 값을 반환해준다.

class Solution:
    def kthSmallestPrimeFraction(self,arr, k):
        left, right = 0, 1
        n = len(arr)
        
        while left < right:
            mid = (left + right) / 2
            cnt = 0
            max_val = 0
            max_i, max_j = 0, 1
            
            j = 1
            for i in range(n - 1):
                while j < n and arr[i] > mid * arr[j]:
                    j += 1
                if j == n:
                    break
                cnt += n - j
                
                if arr[i] / arr[j] > max_val:
                    max_val = arr[i] / arr[j]
                    max_i, max_j = i, j
            
            if cnt == k:
                break
            elif cnt < k:
                left = mid
            else:
                right = mid

        return [arr[max_i], arr[max_j]]

코멘트

이번 문제는 left,right를 0,1로 잡고 이분탐색을 진행해야겠다는 것은 생각했지만 그 후 무엇을 기준으로 이분탐색을 할 것인지는 생각하기 힘들어서 서치를 통해 아이디어를 얻고 코드를 작성했다.