[리트코드(LeetCode)] 215번 Kth Largest Element in an Array

문제

https://leetcode.com/problems/kth-largest-element-in-an-array/

Kth Largest Element in an Array - LeetCode

정렬되지 않은 배열에서 k번째 큰 요소를 추출하는 문제다.

예시

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

 

Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

풀이

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heapify(nums)
        
        for i in range(len(nums) - k):
            heappop(nums)
        
        return heappop(nums)

 

- 가장 첫 번째로 풀었던 방법으로 최소 힙으로 변환되는 heapify를 사용했다.

- K번째로 큰 값을 찾기 위해 (len(nums)-k)번 만큼 최소 값을 순차적으로 제거하면 K번째로 큰 값이 힙의 맨 위로 올라간다.

- 마지막으로 heappop을 사용해 K번째로 큰 값을 반환한다. 

 

# heapq 모듈 이용
heap = list()
for n in nums:
  heappush(heap, -n)

for _ in range(1, k):
  heappop(heap)

print(-heappop(heap))

# 모듈 활용(nlargest)
print(nlargest(k, nums)[-1])

# 정렬
print(sorted(nums, reverse=True)[k - 1])

 

- 책에는 총 4가지 방법으로 푸는 법이 작성되있는데, heapq 모듈(nlargest)이나 정렬을 이용해 풀 경우 더 간단하게 풀 수 있다.

 

참조 : 박상길, 파이썬 알고리즘 인터뷰  https://github.com/onlybooks/algorithm-interview