[LeetCode/리트코드]#668:Kth Smallest Number in Multiplication Table[파이썬/python/이분탐색/Binary Search]

https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/

Kth Smallest Number in Multiplication Table - LeetCode

브루트포스(완전탐색)이나 힙을 이용하여 구현하면 시간초과가 뜬다. 

 

처음에 힙을 이용하여 구현했다가 시간초과를 받았다.

각 n줄에 대하여 가장 작은 사용안한 원소를 힙에서 pop하는 알고리즘

 

시간초과 코드

class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        
        heap=[]
        for i in range(1,m+1):
            for j in range(1,n+1):
                heapq.heappush(heap,-(i*j))

                if len(heap) > k:
                    heapq.heappop(heap)


        return(-heap[0])

이분탐색 코드 (정답)

class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        def search(m,n,k,mid):
            cnt=0
            for i in range(1,m+1):
                cnt+=min(mid//i,n)
                if cnt>=k:
                    return cnt
            return cnt
        
        left=1
        right=m*n
        while left<=right:
            mid = left + (right-left)//2
            if search(m,n,k,mid)>=k:
                right=mid-1
            else:
                left=mid+1
        return left