[파이썬 알고리즘 인터뷰][HEAP] 배열의 K번째 큰 요소

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

정렬되지 않은 배열에서 K번째 큰 요소 추출

 

책에서 구현된 코드

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return sorted(nums, reverse=True)[k - 1]

 

기억해야할 기법

• 정렬이 더 빠르다
  
  • heapify해서 K번째 요소를 찾는 것보다 정렬이 더 빠르다고 한다

 

내가 구현한 코드

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heapq.heapify(nums)
        k = len(nums)-k+1
        while k != 1:
            k-=1
            heapq.heappop(nums)
        return heapq.heappop(nums)

• 뭔가 조건이 더 첨가된 문제를 풀어보면 좋겠다
• K번째 큰 요소는 정렬문제에 가깝고, heap을 써서 무언가 처리가 필요한 문제가 아닌게 아쉽다