[알고리즘/파이썬] 리트코드 leetcode 215. 배열의 K 번째 큰 요소

문제

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

 

풀이 1. heapq 모듈 - heappush, heappop 함수 이용

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = list()
        for n in nums:
            ## - 부호 붙여서 의도적으로 max heap 으로 구성
            heapq.heappush(heap,-n)

        for i in range(k-1):
            heapq.heappop(heap)

        ## 의도적으로 음수 만들어준것을 다시 원래 값으로 복원
        return -heapq.heappop(heap)

풀이 2. heapq 모듈 - heapify 함수 이용

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        ## heapify 함수를 이용하여 한번에 min heap 구조로 만들기
        heapq.heapify(nums)
        
        ## heapify 는 min heap 이기 때문에 k번째 큰 수는 뒤에서 k번째인 수이다.
        ## 뒤에서 k번째 인덱스는 len(nums)-k-1 이다.
        ## k번째 수는 return 해야 하므로 len(nums)-k 번 pop 하고, 마지막 한번은 return 할 때 pop 한다.
        for i in range(len(nums)-k):
            heapq.heappop(nums)

        return heapq.heappop(nums)

풀이 3. heapq 모듈 - nlargest 이용

heapq 모듈에는 n 번째로 큰 값을 추출하는 기능이 있다.

이 기능을 사용하면 한 줄로 처리 가능하다.

heapq — 힙 큐 알고리즘 — Python 3.12.1 문서

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
    	# nlargest 함수 : iterable 에 의해 정의된 데이터 집합에서 n 개의 가장 큰 요소로 구성된 리스트를 반환
        # heapq.nlargest(k,nums): nums 에서 큰 수 k 개로 구성된 리스트를 내림차순으로 반환
        return heapq.nlargest(k,nums)[-1] # 맨 뒤에 값 리턴

 

풀이 4. 정렬 이용

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
    	## 오름차순으로 정렬
        nums.sort()
        ## 뒤에서 k 번째 값 리턴
        return nums[-k]

 

정리

풀이	방식	실행시간
1	heapq 모듈 이용	505 ms
2	heapq 모듈의 heapify 이용	488 ms
3	heapq 모듈의 nlargest 이용	573 ms
4	sort 정렬을 이용	468 ms

 

4가지 방식의 실행 속도에는 큰 차이가 없으나 이 중에서도 파이썬 내장 함수인 sort() 를 이용한  '정렬' 방식이 가장 빠르다.파이썬의 정렬 함수는 팀소트(Timsort)를 사용하며 C로 매우 정교하게 구현되어 있다.

따라서 대부분의 경우에는 파이썬의 내부 정렬 함수를 사용하는 것이 가장 성능이 좋다.

 

문제 출처

Kth Largest Element in an Array - LeetCode

LeetCode - The World's Leading Online Programming Learning Platform