[알고리즘] Leetcode 배열의 K번째 큰 요소

문제 링크

책: 파이썬 알고리즘 인터뷰

heapq 모듈 이용

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = list()
        for n in nums:
            heapq.heappush(heap, -n)

        for _ in range(k-1):
            heapq.heappop(heap)

        return -heapq.heappop(heap)

heapq 모듈의 heapify 이용

    def findKthLargest(self, nums: List[int], k: int) -> int:
        heapq.heapify(nums)

        for _ in range(len(nums) - k):
            heapq.heappop(nums)

        return heapq.heappop(nums)

heapq 모듈의 nlargets 이용

def findKthLargest(self, nums: List[int], k: int) -> int:
    return heapq.nlargest(k, nums)[-1]

정렬을 이용한 풀이

    def findKthLargest(self, nums: List[int], k: int) -> int:
        nums.sort()
        return nums[-k]

의외로 실행 속도에 있어서 큰 차이는 아니지만, '정렬' 방식이 가장 빠르다. 파이썬의 정렬 함수는 팀소트를 사용하며 c로 잘 짜여졌기 때문이다.