- 정렬되지 않은 배열에서 k번째 큰 요소를 추출하라
1. heapq 모듈 이용 (72ms)
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
heap = list()
for n in nums:
heapq.heappush(heap, -n)
for _ in range(k):
heapq.heappop(heap)
return -heapq.heappop(heap)
- 31번 문제 '상위 K 빈도 요소'와 비슷한 문제다. 다른 점이라면 가장 큰 값이냐, 가장 빈번한 값이냐의 차이 정도라 하겠다.
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
freqs = collections.Counter(nums)
freqs_heap=[]
#힙에 음수로 삽입
for f in freqs:
heapq.heappush(freqs_heap, (-freqs[f], f))
#빈도수를 키로, 키를 값으로
topk = list()
#k번 만큼 추출, 최소 힙(Min Heap)이므로 가장 작은 음수 순으로 추출
for _ in range(k):
topk.append(heapq.heappop(freqs_heap)[1])
return topk
-
여기서 함수명을 수정하고,
Cunter()로 빈도 수를 계산해 삽입했던 예전 풀이 대신 값 자체를 힙에 푸시하고 순서만큼 팝하는 형태로 수정한다. -
파이썬
heapq모듈은 최소 힙만 지원하므로, 음수로 저장한 다음 가장 낮은 수부터 추출해 부호를 변환하면 최대 힙처럼 동작하도록 구현할 수 있다.
2. heapq모듈의 heapify 이용 (64ms)
class Solution:
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)
-
모든 값을 꺼내서 푸시하지 않고도 한 번에
heapify()하여 처리할 수 있다.-
heapify()란 주어진 자료구조가 힙 특성을 만족하도록 바꿔주는 연산이며,
이 경우 파이썬의 일반적인 리스트는 힙 특성을 만족하는 리스트로, 값의 위치가 변경된다. -
물론 하나라도 값을 추가하면 다시 힙 특성이 깨지지만, 추가가 계속 일어나는 형태가 아니기 때문에
heapify()는 한 번만 해도 충분하다.
-
3. heapq 모듈의 nlargest 이용 (68ms)
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
return heapq.nlargest(k, nums)[-1]
-
heapq모듈은 강력한 기능을 많이 지원한다.-
그 중
nlargest()는 n 번째 큰 값을 추출한다. -
이 기능을 사용하면, 전체 코드를 한 줄로 처리할 수 있다.
-
-
k번째만큼 큰 값이 가장 큰 값부터 순서대로 리스트로 리턴된다.
- 여기서 마지막 인덱스 -1이 k번째 값이 된다.
-
힙이 아니라도 내부적으로
heapify()함수도 호출해 처리해주기 때문에, 별도로 힙 처리를 할 필요가 없어 편리하다. -
참고로
nsmallest()를 사용하면 동일한 방식으로 n번째 작은 값도 추출이 가능하다.
4. 정렬을 이용한 풀이 (56ms)
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
return sorted(nums, reverse=True)[k-1]
-
이번에는 정렬부터 한 다음, k번째 값을 추출하는 방식으로 풀이해본다.
-
추가, 삭제가 빈번할 때는
heapq를 이용한 힙 정렬이 유용하지만 이처럼 입력값이 고정되어 있을 때는 그저 한 번 정렬하는 것만으로 충분하다.
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
nums.sort()
return nums
sorted()로 큰 값부터 역순으로 정렬하면, 다음과 같이 좀 더 직관적인 풀이도 가능하다.
- 모든 방식은 실행 속도에 큰 차이가 없으나 '정렬' 방식이 가장 빠르다. 파이썬의 정렬함수는 팀소트를 사용하여 C로 매우 정교하게 구현되어 있기 때문에, 대부분의 경우에는 파이썬의 내부 정렬 함수를 사용하는 편이 가장 성능이 좋다.
Studying Computer Science