https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/
브루트포스(완전탐색)이나 힙을 이용하여 구현하면 시간초과가 뜬다.
처음에 힙을 이용하여 구현했다가 시간초과를 받았다.
각 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