99클럽 코테 스터디 29일차 TIL, 정렬(Top K Frequent Elements)

1. 문제 정의

2. 문제 접근

각 숫자가 반복된 숫자를 map에 담아주고 정렬하여 정답을 리턴하면 된다.

3. 문제 풀이

1. map에 각 number가 몇번 반복됐는지 담는다.
2. 리스트 배열에 옮겨 담는다.
3. 정답을 리턴한다.

4. 코드

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        int[] answer = new int[k];
        List<Integer>[] list = new ArrayList[nums.length + 1];
        Map<Integer, Integer> map = new HashMap<>();

        for(int n:nums){
            map.put(n,map.getOrDefault(n,0)+1);
        }

        for (int key : map.keySet()) {
            int num = map.get(key);
            if (list[num] == null) {
                list[num] = new ArrayList<>();
            }
            list[num].add(key); // num = 반복 횟수, key = num
        }

        int idx = 0;
        for(int i = list.length-1; i >= 0; i--){
            if(list[i] != null){
                for(int j = 0; j < list[i].size() && idx < k; j++){
                    answer[idx] = list[i].get(j);
                    idx++;
                }
            }
        }
        return answer;
    }
}

 

5. 회고

처음에는 간단한 문제라고 생각했는데, 정렬을 하려니 머리가 아픈 문제다. map에 담는거부터 시작이다. map에 담겨있는걸 어떻게 정렬할지에 대해서가 관건인데, entrySet을 꺼내어 정렬하는 방법은 복잡해보였다. 다른 방법으로 정렬해서 넣을 수 있는 방법이 없을까 생각하다 리스트를 생각하게 됐다. 반복횟수가 유니크한 값이 아니기에 List[]을 이용하였다. 정렬 문제를 또 이렇게 어렵게 낼 수 있겠구나?하는 생각이 들었다.