(Heap, Medium) Top K Frequent Elements

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

문제 종류가 Heap이고, 빈도 수가 가장 높은 k개의 숫자를 배열로 리턴하란다.
그럼 먼저 떠오른게 PriorityQueue인데, 문제는 뭘 기준으로 정렬하느냐다.

당연히 정렬은 빈도다.
근데 빈도는 아직 모른다.
그럼 빈도 먼저 O(n)으로 계산해서 맵에 넣어 두고, PriorityQueue의 정렬방식을 빈도 수 기준으로 내림차순 해주면 되겠다.

맵의 각 entry를 PriorityQueue에 넣고, 최종적으로는 k개만 꺼내서 정답 배열에 주면 된다.

문제에서 요구하는 시간복잡도가 O(n log n)인데,
빈도수 구하기 O(n)이고 이걸로 구해진 맵에다 힙 연산이므로 n log n 해서 결국 O(N log N)이다.

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        
        Map<Integer, Integer> map = new HashMap<>();
        for (int n : nums) {
            map.put(n, map.getOrDefault(n, 0) + 1);
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o2[1] - o1[1]);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            pq.offer(new int[] { entry.getKey(), entry.getValue() });
        }

        int[] result = new int[k];
        for (int i=0; i<k; i++) {
            result[i] = pq.poll()[0];
        }

        return result;
    }
}

애초에 힙에 k개만 유지하도록 코딩하면 (size > k 일 때 poll) 힙 연산에 드는 비용을 더 줄일 수도 있다.