LeetCode - 배열의 K번째 큰 요소 [Python3] #heapq

문제 출처

📌 문제

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

• 입력
  [3,2,3,1,2,4,5,5,6], k=4
• 출력
  4

🐶 풀이 1) heapq 모듈 이용

파이썬 heapq 모듈은 최소 힙만 지원하므로,
최대 힙을 구현하기 위해서는 음수로 저장한 다음 가장 낮은 수부터 추출해 부호를 변환하면 된다!

def findKthLargest(self, nums: List[int], k: int) -> Int:
	heap = list()
    for n in nums:
    	heapq.heappush(heap, -n)
        
    for _ in range(1, k):
    	heapq.heappop(heap)
        
    return -heapq.heappop(heap)

🐶 풀이 2) heapq 모듈의 heapify 이용

풀이 1에서 모든 값을 푸시하지 않아도 한 번에 heapify()하여 처리할 수 있다.

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)

🐶 풀이 3) heapq 모듈의 nlargest 이용

nlargest() : n번째 큰 값을 추출하는 heapq 모듈의 기능 중 하나. k번째만큼 큰 값이 가장 큰 값부터 순서대로 리스트로 리턴된다.
nsmallest() : n번째 작은 값을 추출하는 heapq 모듈의 기능 중 하나

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

🐶 풀이 4) 정렬을 이용한 풀이

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