[Python] Leetcode - Top K Frequent Elements

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

Top K Frequent Elements - LeetCode

# 문제해설: nums 배열과 k가 주어졌을때, nums배열에서 가장 자주 등장하는 k개의 수를 return해라.

                (순서는 상관없다)

 

# heap을 사용해서 푸는 간단한 문제이다.

# defaultdict을 사용해 cnt에 nums의 숫자들의 갯수를 저장해준다. (Counter함수 사용해도 됨!)

   cnt에 저장된 숫자들(i)를 h라는 힙에 (cnt[i], i)형식으로 heappush해준다.

   (힙은 cnt[i] 즉, i의 갯수 순으로 내림차순 정렬됨)

 

# 그리고 힙의 원소갯수가 k개를 넘는다면

   heap의 가장 마지막 원소(갯수가 가장 작은 number)를 pop해준다.

   

   최종적으로 힙에 남은 k개의 원소가 답이 된다.

 

import heapq
from collections import defaultdict
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        h = []
        cnt = defaultdict(int)
        for i in nums:
            cnt[i] += 1

        for i in cnt:
                heapq.heappush(h, (cnt[i], i))
                if len(h) > k:
                    heapq.heappop(h)
        
        ans = []
        for i in h:
            ans.append(i[1])
        return ans