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

문제링크:

2910번: 빈도 정렬

 

문제:

위대한 해커 창영이는 모든 암호를 깨는 방법을 발견했다. 그 방법은 빈도를 조사하는 것이다.

 

창영이는 말할 수 없는 방법을 이용해서 현우가 강산이에게 보내는 메시지를 획득했다. 이 메시지는 숫자 N개로 이루어진 수열이고, 숫자는 모두 C보다 작거나 같다. 창영이는 이 숫자를 자주 등장하는 빈도순대로 정렬하려고 한다.

 

만약, 수열의 두 수 X와 Y가 있을 때, X가 Y보다 수열에서 많이 등장하는 경우에는 X가 Y보다 앞에 있어야 한다. 만약, 등장하는 횟수가 같다면, 먼저 나온 것이 앞에 있어야 한다.

 

이렇게 정렬하는 방법을 빈도 정렬이라고 한다.

 

수열이 주어졌을 때, 빈도 정렬을 하는 프로그램을 작성하시오.

 

입력:

첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000)

둘째 줄에 메시지 수열이 주어진다

 

출력:

첫째 줄에 입력으로 주어진 수열을 빈도 정렬한 다음 출력한다.

 

 

문제이해:

입력으로 주어진 숫자들을 정렬하는 문제라고 하면 흔히 숫자의 크기대로 오름차순 또는 내림차순 정렬하는 것을 떠올릴 수 있다. 하지만 이 문제의 핵심은 숫자가 등장한 ‘빈도’다. 즉, 어떤 숫자가 더 자주 나왔는지가 정렬의 기준이 된다. 여기에 더해, 빈도수가 같은 숫자들끼리는 원래 입력된 순서를 그대로 유지해야 한다는 조건이 있다.

 

예를 들어 1 1 2 2 2 3 3 4 5 6이라는 수열이 주어졌다고 하자. 이 수열에서 숫자 2는 3번 등장하고, 1과 3은 각각 2번, 나머지는 1번씩 등장한다. 따라서 가장 자주 등장한 2가 먼저 출력되고, 그다음은 등장 횟수가 같은 1과 3이 등장한다. 이 둘은 빈도는 같지만 1이 먼저 입력되었기 때문에 1이 앞에 온다. 나머지 숫자들도 입력 순서를 그대로 유지하며 출력된다. 결과는 2 2 2 1 1 3 3 4 5 6이 된다.

 

이 문제는 정렬 기준이 숫자의 값이 아니라 등장 빈도와 입력 순서라는 점에서 흥미롭다. 일반적인 정렬 함수나 비교기를 사용하기보다는, 자바의 HashMap을 활용하여 숫자의 빈도를 계산하고, 입력 배열을 그대로 활용해 순서를 유지하는 방식으로 구현할 수 있다. 또한, 이미 출력한 숫자가 다시 출력되지 않도록 하기 위해 HashSet을 이용해 중복을 제거하는 로직도 함께 사용된다.

 

이처럼 빈도 정렬 문제는 단순한 정렬 문제를 넘어, 해시 기반의 자료구조를 어떻게 활용할지에 대한 사고력을 기를 수 있는 좋은 예제다.

 

정답코드:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
    static HashMap<Integer, Integer> frequency;
    static int[] input;
    static int[] inputFrequency;
    static StringBuilder sr;
    static int N, C;

    public static void frequencySort() {
        sr = new StringBuilder();

        // 빈도 계산
        for (int i = 0; i < input.length; i++) {
            frequency.put(input[i], frequency.getOrDefault(input[i], 0) + 1);
        }

        // 각 숫자의 빈도를 배열에 저장
        for (int i = 0; i < input.length; i++) {
            inputFrequency[i] = frequency.get(input[i]);
        }

        // 최댓값(최대 빈도) 찾기
        int max = 0;
        for (int i = 0; i < input.length; i++) {
            if (inputFrequency[i] > max) {
                max = inputFrequency[i];
            }
        }

        // 이미 출력한 숫자인지 체크하기 위한 HashSet
        HashSet<Integer> visited = new HashSet<>();

        // 최대 빈도부터 1까지 내려가면서 출력
        while (max != 0) {
            for (int i = 0; i < input.length; i++) {
                if (inputFrequency[i] == max && !visited.contains(input[i])) {
                    visited.add(input[i]);
                    for (int j = 0; j < max; j++) {
                        sr.append(input[i]).append(" ");
                    }
                }
            }
            max--;
        }
    }

    public static void main(String[] args) throws IOException {
        frequency = new HashMap<>();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // N과 C 입력
        N = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        // 숫자 입력
        input = new int[N];
        inputFrequency = new int[N];

        String inputString = br.readLine();
        String[] parts = inputString.split(" ");
        for (int i = 0; i < N; i++) {
            input[i] = Integer.parseInt(parts[i]);
        }

        // 빈도 정렬 수행
        frequencySort();

        // 결과 출력
        System.out.println(sr.toString());
    }
}

 

마무리하며:

이 문제를 해결하고 나서 다른 사람들의 풀이를 찾아보니, 대부분은 리스트 정렬이나 Comparator를 활용해서 훨씬 간결하고 효율적으로 구현한 경우가 많았다. 반면 작성자는 그런 정렬 방식을 사용하지 않고 조건문과 반복문으로 풀다 보니 코드가 조금 지저분하고 비효율적인 감이 없지 않아 아쉬움이 남는다. 그래도 결과적으로 문제를 제대로 해결했고, 동작하는 코드가 나왔다는 점에서 의미 있다고 생각한다.

 

감사합니다.