기억하고싶은것들

Given an integer array nums and an integer k, return the k most frequent elements.

You may return the answer in any order.

입력값으로 integer 배열과 integer k를 받는다. 가장 많이 등장하는 k개의 요소들을 반환하라.

어떠한 순서로 반환해도 상관없다.

가장 큰 값이나, 가장 작은 값을 찾는 문제와 비슷하게 가장 많이 등장하는 k개의 요소를 찾는 문제이므로

Heap을 이용하는 Priority Queue를 사용해서 찾으면 될 것이다.

Priority Queue를 구성하기 전에 비교하는 값이 등장하는 횟수이므로, 횟수를 비교 가능한 Map을 구성한 후에 Heap에 요소로 사용해보자.

    public static int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>(); // 등장 횟수 Count
        for (int i : nums) {
            map.put(i, map.getOrDefault(i, 0) + 1);
        }

        PriorityQueue<Map.Entry<Integer, Integer>> queue = 
            new PriorityQueue<>((a, b) -> b.getValue() - a.getValue()); // 내림차순
        queue.addAll(map.entrySet());

        int[] rst = new int[k];
        for (int i = 0; i < k; i++) {
            rst[i] = queue.poll().getKey();
        }
        return rst;
    }

먼저 Map을 이용하여 주어진 Nums의 요소들이 등장하는 횟수를 카운트 해준다.

후에, 해당 Map을 기준으로 Priority Queue를 구성해준다.

Queue의 비교대상은 Map의 Key가 아닌 Value이다. ( 등장 횟수 )

이제 Priority Queue가 등장 횟수 순으로 정렬이 되었으므로, 입력값이 k만큼 Queue에서 Poll 해주면 된다.