LeetCode No.215 (T)

LeetCode No. 215 Kth Largest Element in an Array

숫자 배열 nums와 숫자 k가 주어진다. 해당 배열에서 k번째로 큰 수를 반환하라.

---

제한 범위

1 <= k <= nums.length <= 104
-104 <= nums[i] <= 104

---

처음 내 생각

• 오잉? 싶었다. 정렬하고 뽑아내면 되잖아?

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

• 진짜 되잖아??

---

조금만 더 생각해보자

• 문제의 카테고리를 봤다. 내장된 정렬 기능을 쓰라고 낸 문제는 아닐 터.
• 여러 가지 태그가 나왔다. 우선순위 큐, 힙, 분할 정복법 등..
• 그래서, 출제 의도 중 하나인 힙을 사용해서 다시 풀어 보았다.

import heapq

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

• 대강 비슷한 느낌이긴 하지만...
• 힙의 특성을 알아 두면, 특정한 상황에서 써봄직하다는 생각은 들었다.
• 대개의 내장 정렬 메서드는 O(nlogn)만큼의 시간이 걸린다. 힙을 사용함으로써 이 제약을 완화할 수 있다면, 힙을 사용하는 것도 좋아 보인다.