[LeetCode 215] Kth Largest Element in an Array

 

Think

https://www.youtube.com/watch?v=XEmy13g1Qxc 

 

k번째 큰 수를 찾는 문제.

자연스럽게 정렬을 생각하게 되는데,

위 영상에서 그냥 정렬을 하면 O(nlogn)의 시간이 들지만

힙으로 만들면 정렬 시간을 O(n) 으로 줄일 수 있다고 한다.

대신 힙으로 만들어서 제일 큰 수부터 하나씩 꺼낼 경우,

꺼낼 때마다 logn 의 시간이 든다.

따라서 k번째 큰 수를 찾으려면 n+klogn 의 시간이 들게 된다.

이는 대체적으로 nlogn보다 좋은 값이지만, k값에 따라서 더 오래 걸리는 경우도 있다.

평균적으로 보았을 때에는 더 좋은 값이라고 할 수 있다.

 

파이썬의 heapq모듈을 활용한다.

heapq모듈은 최소힙이므로,

음수로 바꾸어서 힙에 저장한 다음 가장 작은 수부터 pop하도록 하고 양수로 바꾸면 k번째 큰요소가 된다

 

 

Solution

class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        heap = list()
        for n in nums : 
            heapq.heappush(heap, -n)
            
        for _ in range(1, k) : #k-1번 실행됨
            heapq.heappop(heap)
        
        return -heapq.heappop(heap) #k번째 pop실행해서 양수로 바꾸어 반환

 

 

 

Get