[Baekjoon] 백준 2910번: 빈도 정렬 (JAVA)

문제 2910번

2910번: 빈도 정렬

[ 문제 풀이 ]

수열에서 등장하는 횟수가 많은 순으로 정렬을 해야 합니다. 횟수가 동일한 경우에는 수열에서 먼저 나온 숫자가 앞에 있어야 하므로 2가지의 정렬 조건을 만족해야 합니다.

숫자를 key로 하고, 해당 숫자가 나온 빈도를 value값으로 하는 HashMap을 만들고, 이 HashMap의 keySet에 위의 2가지 정렬 조건을 정의해주면 됩니다. keySet의 sort()를 사용하여 람다 함수로 구현하였습니다.

두 수의 등장하는 횟수가 동일한 경우에 어느 수가 앞에 위치하는지를 알기 위해서 order라는 HashMap을 하나 더 만들어서 숫자를 하나씩 입력받을 때 order에 해당 숫자를 key로 가지는 데이터가 아직 없는 경우, 해당 숫자를 key로 하고 해당 숫자의 인덱스를 value로 하여 order에 저장합니다. 1 2 1 1 수열인 경우, 아직 1을 key로 가지는 데이터가 order에 없기 때문에 [1, 0] (key: 1, value:0) 숫자 1의 위치를 인덱스 0으로 저장하여 같은 1 중에서도 가장 앞에 있는 숫자의 위치를 저장하게 됩니다.

[ 코드 ]

import java.io.*;
import java.util.*;

public class Main {
    private static HashMap<Integer, Integer> map = new HashMap<>();
    private static HashMap<Integer, Integer> order = new HashMap<>(); // 키: 숫자, 값: 순서

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int n = Integer.parseInt(st.nextToken());
            if (!order.containsKey(n)) order.put(n, i);
            map.put(n, map.getOrDefault(n, 0) + 1);
        }

        List<Integer> keySet = new ArrayList<>(map.keySet());
        keySet.sort((o1, o2) -> {
            if (Objects.equals(map.get(o1), map.get(o2))) {
                return order.get(o1).compareTo(order.get(o2)); // 인덱스 작은 순서
            }
            return map.get(o2).compareTo(map.get(o1));
        });

        for (int key: keySet) {
            for (int i = 0; i < map.get(key); i++) {
                bw.write(key + " ");
            }
        }
        bw.flush();
    }
}