LeetCode No.215 (T)

radiantchoi·2022년 5월 3일
0

Algo-log

목록 보기
2/13

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)만큼의 시간이 걸린다. 힙을 사용함으로써 이 제약을 완화할 수 있다면, 힙을 사용하는 것도 좋아 보인다.
profile
함께 나아가고자 하는 사람

0개의 댓글