15. 해시 - 상위 K 빈도 요소(우선순위 큐, *,zip)

https://leetcode.com/problems/top-k-frequent-elements/

Top K Frequent Elements - LeetCode

 

 

풀이 1. Counter를 이용한 음수 순 추출

 요소의 값을 키로 하는 해시 테이블을 만들고 여기에 빈도 수를 저장한 다음, 우서눈위 큐(Priority Queue)를 이용해 k번만큼 추출하면 k번 이상 등장하는 요소를 손쉽게 추출할 수 있다.

 파이썬에서 우선순위 큐는 힙을 활용하는 heapq 모듈을 사용한다.

 

 이제 힙세 삽입해보자. 삽입 방식은 2가지가 있는데 첫째는 파이썬의 리스트에 모두 삽입한 다음 마지막에 heapify()를 하는 방식과, 두 번째는 매번 heappush()를 하는 방식이다. heappush()로 삽입하게 되면 매번 heapify()가 일어나기 때문에 별도로 처리할 필요가 없다. 이 방식이 원래 힙의 삽입 방식이기도 하다. 여기서는 후자인 heappush()로 처리해본다.

 

# Counter를 이용한 음수 순 추출
import collections
import heapq

class Solution():
    def topFrequent(self,nums,k):
        freqs=collections.Counter(nums)
        freqs_heap=[]
       

        # 힙에 음수로 삽입
        for f in freqs:
            heapq.heappush(freqs_heap,(-freqs[f],f))  #(힙,(key(우선순위),value)) 파이썬은 min_heap만 지원

        topk=list()

        for _ in range(k):
            topk.append(heapq.heappop(freqs_heap)[1])

        return topk

 여기서는 빈도 수를 키로 하고, freqs의 키를 값으로 했다. 즉 키/값을 바꿔서 힙에 추가했다. 파이썬 heapq 모듈은 최소 힙만 지원한다.

 

풀이 2. 파이썬 다운 방법

class Solution:
    def topKFrequent(self,nums,k):
        return list(zip(*collections.Counter(nums).most_common(k)))[0]