99클럽 코테 스터디 14일차 TIL Leetcode K-th Smallest Prime Fraction

K-th Smallest Prime Fraction

오늘의 이분탐색 문제였는데.. heap 자료구조로 풀었다.

내 접근 방법은 다음과 같다.

가장 작은 수는 맨 앞 수인 1과 맨 뒤에 있는 임의의 수인 arr[-1]로 나눈 값이다.

그렇다면 그 다음 작은수는 자연스럽게  - 분자가 1 다음에 나오는 수 또는 분모가 맨뒤 앞에 나오는수로 둘 중 하나를 바꿔주면 된다. 그 둘을 힙 구조에 넣고, 가장 작은 값을 빼면, 항상 가장 작은 값이 나오므로, 답을 구할 수 있다.

주의해야할 점은 중복이 생기지 않게 해야한다는 점인데, 나는 그냥 튜플로 순서쌍을 저장해서 체크했다. 

 

나의 코드

class Solution:
    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
        queue=[]
        idx1=0
        idx2=len(arr)-1
        check={}
        heappush(queue,[arr[idx1]/arr[idx2],idx1,idx2])
        check[(idx1,idx2)]=True
        for _ in range(k):
            value,idx1,idx2=heappop(queue)
            if idx1+1<idx2:
                if not check.get((idx1+1,idx2)):
                    heappush(queue,[arr[idx1+1]/arr[idx2],idx1+1,idx2])
                    check[(idx1+1,idx2)]=True
                if not check.get((idx1,idx2-1)):
                    heappush(queue,[arr[idx1]/arr[idx2-1],idx1,idx2-1])
                    check[(idx1,idx2-1)]=True
        return [arr[idx1],arr[idx2]]

 

오늘의 회고

이분탐색이라는 카테고리가 정해졌지만, 나는 힙 자료구조밖에 생각나지 않아 힙으로 풀었다.

해답을 봤지만, 아직 이런류의 이분탐색 문제는 익숙하지 않은 것 같다.

더 접근법을 자연스럽게 생각해보기 위해 공부해봐야겠다..