[해시 테이블] 상위 K 빈도 요소

347 | Top K Frequent Elements
https://leetcode.com/problems/top-k-frequent-elements/

 

 

 

작성 코드

 

접근 방법

1. Counter 객체를 활용하여 빈도수 정렬한 후 key 값 가져와서 k 만큼 슬라이싱한 배열을 return

 

import collections
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        answer = []
        a = collections.Counter(nums)
        for i in a: 
            answer.append(i)
            if len(answer) == k:
                return answer

 

•  a = Counter({0: 2, 3: 1, 1: 1})  으로 잘 정렬되었는데, for 문을 돌 때 순서가  [3, 0, 1]  로 되어버림, 원인 파악 중

 

 

이상 코드

 

Counter를 이용한 음수 순 추출

 

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freqs = collections.Counter(nums)
        freqs_heap = []
        # key - 빈도수, value - freqs의 키
        for f in freqs:
            heapq.heappush(freqs_heap, (-freqs[f], f))

        topk = list()
        # k번 만큼 추출, 민 힙 이므로 가장 작은 음수 순으로 추출
        for _ in range(k):
            topk.append(heapq.heappop(freqs_heap)[1])

        return topk

 

• 힙은 키 순서대로 정렬
• 음수로 저장한 이유는 파이썬 heapq 모듈은 최소 힙만 지원하기 때문

 

 

파이썬 다운 방식

 

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

 

• most_common 값은  [(1, 3), (2, 2)]   을 반환, zip을 통해  [(1, 2), (3, 2)]  반환