[LeetCode | Python] 347. Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

빈도수가 높은 순서대로, 상위 k개의 elements를 출력하는 문제다.

 

풀이 1

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = defaultdict(int)
        
        for i in nums:
            count[i] += 1
        
        result = sorted(count, key=count.get, reverse=True)[:k]
        return result

처음 푼 풀이다.

defaultdict(int)로 선언하고 nums 배열을 한번 순회하면서 빈도를 셌다.

sorted(count, key=count.get, reverse=True)[:k]

sorted(정렬대상, 정렬기준, 정렬순서)에서, 정렬 기준에 count.get을 넣어준다.

딕셔너리 get 메서드는 key를 기준으로 value를 가져온다.

그 후 상위 k개의 요소를 [:k]로 슬라이싱하여 반환한다.

 

풀이2: sorting (neetcode 풀이)

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = {}
        for num in nums:
            count[num] = 1 + count.get(num, 0)

        arr = []
        for num, cnt in count.items():
            arr.append([cnt, num])
        arr.sort()

        res = []
        while len(res) < k:
            res.append(arr.pop()[1])
        return res

sorting한 후 pop하여 마지막 요소를 제거 -> 빈도가 높은 순서대로 res 배열에 저장하게 된다.

while len(res) < k: 아이디어는 참고하면 좋을 듯

 

풀이3: heap (neetcode 풀이)

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = {}
        for num in nums:
            count[num] = 1 + count.get(num, 0)

        heap = []
        for num in count.keys():
            heapq.heappush(heap, (count[num], num))
            if len(heap) > k:
                heapq.heappop(heap)

        res = []
        for i in range(k):
            res.append(heapq.heappop(heap)[1])
        return res

heap을 사용해서도 풀 수 있다.

최소 힙을 사용하여, k개 이상의 요소가 쌓이면 최소값을 제거한다. 결과적으로 빈도수가 높은 k개의 요소만 남게 된다.