[백준] 2910번 : 빈도 정렬 – JAVA [자바]

https://www.acmicpc.net/problem/2910

2910번: 빈도 정렬

 

---

• 문제

 

 

---

• 문제 풀이

백준 2910번은 실버 3 난이도의 정렬 및 해시 문제이다. 이 문제에서는 숫자 N개가 주어진다. 이때, 이 숫자들을 가장 자주 등장하는 빈도수대로 정렬을 하면 된다. 추가로, 등장하는 횟수가 같으면 먼저 나온 숫자가 앞에 나오게 하면 된다. 

 

이 문제를 풀려면 우선 해시맵을 이용해서 숫자들의 빈도수를 입력받아야 한다. 이 빈도수는 나중에 정렬을 할 때 필요하다.

 

추가로, 아래에 있는 코드를 보면 알겠지만, 리스트를 2개 만들었다. 리스트 list는 실제 정렬을 할 리스트이고 리스트 original은 처음에 들어오는 숫자들을 입력받는 리스트이다. 이 original 리스트가 필요한 이유는, 빈도수가 같을 때 먼저 나오는 숫자가 앞에 오게 해야 되는데, 이때 숫자의 첫 인덱스가 필요하다. 이 인덱스를 original 리스트에서 구한다.

 

이제 이 문제를 풀 때 가장 중요한 로직인 정렬을 살펴보겠다. 정렬 부분 코드는 다음과 같다.

 

// 빈도수를 기준으로 리스트를 정렬
Collections.sort(list, (o1, o2) -> {
    if (map.get(o1) == map.get(o2)) { // 빈도수가 같을 경우, 원래 입력 순서를 유지하도록 한다.
        return original.indexOf(o1) - original.indexOf(o2);
    } else { // 빈도수가 다른 경우, 빈도수를 기준으로 내림차순 정렬
        return Integer.compare(map.get(o2), map.get(o1));
    }
});

 

우선, 첫 번째 부분, 즉 빈도수가 같을 때는 원래 입력을 받은 순서를 유지해야 한다. 따라서 이때 original 리스트를 사용한다. 만약에 빈도수가 다른 경우는 빈도수를 기준으로 내림차순으로 정렬을 해주면 된다.

 

자세한 코드는 아래에 있는 코드를 참고하면 되겠다.

 

---

• 코드

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 입력값 받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 메시지의 길이 N
        int c = Integer.parseInt(st.nextToken()); // 수의 범위 C
        List<Integer> list = new ArrayList<>(); // 입력 수열을 저장할 리스트
        st = new StringTokenizer(br.readLine());

        // 각 숫자의 빈도수를 저장하는 해시맵
        Map<Integer, Integer> map = new HashMap<>();

        // 입력 수열을 리스트에 저장하고 빈도수를 해시맵에 기록
        List<Integer> original = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(Integer.parseInt(st.nextToken()));
            original.add(list.get(i));
            map.put(list.get(i), map.getOrDefault(list.get(i), 0) + 1);
        }

        // 빈도수를 기준으로 리스트를 정렬
        Collections.sort(list, (o1, o2) -> {
            if (map.get(o1) == map.get(o2)) { // 빈도수가 같을 경우, 원래 입력 순서를 유지하도록 한다.
                return original.indexOf(o1) - original.indexOf(o2);
            } else { // 빈도수가 다른 경우, 빈도수를 기준으로 내림차순 정렬
                return Integer.compare(map.get(o2), map.get(o1));
            }
        });

        // 정렬된 리스트를 출력
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(list.get(i) + " ");
        }
        System.out.println(sb);
    }
}