📚 단일 패턴

347. Top K Frequent Elements

MinHeap을 사용하여 배열에서 가장 빈번하게 나타나는 상위 K개의 요소를 찾기

Oct 1, 2025 — heap

문제 설명

LeetCode 347. Top K Frequent Elements (opens in a new window)
나에게 Heap , Priority Queue 의 유용함을 알게 해준 첫번째 문제.

풀이 아이디어

아래 구현은 leetcode 에서 기본 제공하는 MinPriorityQueue 을 이용해서 minHeap을 구현한 것이라서 이 부분은 달라질 수 있음.
가장 많이 나온 top K 번째 숫자를 구하기 위해서
size K 인 minHeap 을 만들어서 (maxHeap 이 아님)
- [ value, freq ] 넣고
- minHeap 은 freq 값으로 sorting되도록 함.
minHeap 이므로 값이 큰 것들은 계속 남아 있을 것이고, 작은 것들은 계속 빠질 것이다.
minHeap 이 K size 보다 커지면 (K+1) 사이즈에서 가장 작은 값을 빼내면 이후 K 개 값이 유지된다.
최종 minHeap 에서 값을 추출하면 가장 많이 나온 top K 번째 숫자를 구할 수 있다.

구현

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
    const freqs = new Map();

    for (const num of nums) {
        freqs.set(num, (freqs.get(num) || 0) + 1)
    }

    const minHeap = new MinPriorityQueue({ compare: (a,b) => a[1] - b[1] });

    for (const freq of freqs.keys()) {
        minHeap.enqueue([ freq, freqs.get(freq) ]);
        if (minHeap.size() > k) minHeap.dequeue();
    }

    return minHeap.toArray().map(([ value, freq ]) => value);
};