[백준][10989번: 수 정렬하기 3]

문제

링크텍스트

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

입력

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

출력

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

코드

import java.io.*;

public class Main{
    static int N;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        int[] count = new int[10001];
        for(int i=0; i<N; i++){
            int num = Integer.parseInt(br.readLine());
            count[num]++;
        }
        StringBuilder sb = new StringBuilder();
        // Counting sort - 계수 정렬 이용
        for(int i=1; i<10001; i++){
            for(int j=0; j<count[i]; j++){
                sb.append(i).append('\n');
            }
        }
        System.out.println(sb.toString());
    }
}

알고 넘어가기

처음에 list라는 int배열을 만들고 Arrays.sort()로 오름차순을 한뒤 반복문을 통해서 출력했다. 그 결과로는 시간초과가 났다. 그 이유는 N <= 10000000 이고, Arrays.sort()는 O(N^2)이 걸리기 때문에 10000000^2의 경우는 100000000000000이라는 큰 수이므로 시간초과가 난다. 그래서 다른 방법인
Counting Sort - 계수 정렬을 사용했다.
계수 정렬이란 ?
1. 해당 값과 다른 값들과 비교하는 것이 아니라 해당 값이 몇개가 있는지 개수를 세서 정렬하는 방법이다.
2. 양의 정수여야 한다.
3. 정렬을 위한 길이 n의 배열 하나, 계수를 위한 길이 k의 배열 하나. O(n+k) 의 공간복잡도를 가진다.