[백준] #10989 - 수 정렬하기 3

🔒 문제 설명

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

---

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

---

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

🔑 해결 아이디어

이번 문제의 핵심은 사실 정렬 방법 이 아니었다. 정렬은 단순한 우선순위 큐나, quickSort 를 사용하면 된다. (quickSort의 방법이 우선순위 큐 보다 미세하게 성능이 더 좋았다. )

문제의 핵심은 입력 조건이었다. 입력되는 수의 개수 $N$의 조건은 $1 \le N \le 10,000,000$ 이었기에, $O(nlog(n))$의 시간으로 정렬을 하더라도 상당한 시간이 걸린다. 다만, 입력되는 수가 10,000보다 작거나 같은 자연수라는 조건을 함께 생각하면 훨씬 정렬이 간단해 진다.

단순히 10,000개의 수를 정렬하는 데 걸리는 시간은 10,000,000개의 수를 정렬하는 시간보다 훨씬 짧기 때문이다. 두 조건은 입력받는 수에 많은 중복이 포함되어 있다는 것을 의미하므로, 입력받는 수들의 개수를 기억하는 것이 핵심이다.

💻 소스코드

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

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

        List<Integer> list = new LinkedList<>();
        int size = Integer.parseInt(br.readLine());
        HashMap<Integer, Integer> count = new HashMap<>();
        for(int i = 0; i<size; i++) {
            int input = Integer.parseInt(br.readLine());
            if(count.containsKey(input)){
                count.put(input, count.get(input) + 1);
            }
            else{
                list.add(input);
                count.put(input, 1);
            }
        }
        br.close();

        Collections.sort(list);
        Iterator<Integer> iterator = list.iterator();

        while (iterator.hasNext()) {
            int number = iterator.next();
            int numberNum = count.get(number);

            for (int i = 0; i < numberNum; i++) {
                bw.write(Integer.toString(number) + "\n");
            }
        }

        bw.flush();
        bw.close();

    }
}