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

출처 : https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

1. 문제

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

 

---

2. 입력

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

 

10
5
2
3
1
4
2
3
5
1
7

---

3. 출력

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

 

1
1
2
2
3
3
4
5
5
7

 

---

4. 풀이

문제에서 처음부터 입력받는 숫자들의 범위가 1~10000으로 이미 정해져 있고, 입력받는 숫자들의 개수 또한 최대 10000000으로 10000보다 훨씬 크므로 카운팅 정렬을 사용하면 시간복잡도 O(n)의 효율로 배열을 정렬할 수 있다. 

---

5. 소스코드

import java.io.*;

class Main{
    static int [] temp;
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int num = Integer.parseInt(br.readLine());
        int [] arr = new int [num];
        for(int i=0; i<num; i++) arr[i] = Integer.parseInt(br.readLine());

        int [] c_arr = new int [10001];
        for(int i=0; i<num; i++) c_arr[arr[i]]++;
        c_arr[0] = 0;
        for(int i=0; i<10000; i++) c_arr[i+1] += c_arr[i];
        int [] result = new int [arr.length];
        for(int i=num-1; i>=0; i--){
            result[c_arr[arr[i]]-1] = arr[i];
            c_arr[arr[i]]--;
        }

        for(int a : result) {
            sb.append(a);
            sb.append('\n');
        }
        System.out.println(sb);
    }
}

---

6. 배운 것

정렬할 숫자들의 범위가 한정적이라면 카운팅 정렬을 통해 빠르게 정렬을 할 수 있다.

 

또한, 문제를 풀며 시간초과를 접하게 되었는데 이는 System.out.println 대신 StringBuilder를 사용할 수 있고, Arrays.sort 함수를 이용 시 간편하지만 무겁기에 카운팅 정렬 방식을 잘 활용하면 속도 또한 올릴 수 있다.