[백준] 수 정렬하기 - 3 [자바/Java]

문제:https://www.acmicpc.net/problem/10989

코드:https://github.com/irerin07/AlgorithmStudyBaek/blob/master/src/baekjoon/baekjoon10989.java

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

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

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[10001];
        for(int i = 0; i < n; i++){
            arr[Integer.parseInt(br.readLine())]++;
        }
        for (int i = 1; i < 10001; i++) {
            while (0 < arr[i]--) {
                bw.write(i + "\n");
            }
        }
        br.close();
        bw.close();
    }
}

 

"수의 범위가 작다면 카운팅 정렬을 사용하여 더욱 빠르게 정렬할 수 있다."

 

수의 범위만큼의 크기를 가진 배열을 만들어서

각 배열의 i마다 각 수가 몇번 나왔는지 저장을 한다.

모든 수의 입력이 끝났다면 맨 처음부터 각 인덱스의 있는 수를 하나씩 빼면서 해당 인덱스를 출력한다.

 

10 5 2 3 1 4 2 3 5 1 7

위와 같은 예제가 주어지는데

맨 앞의 수는 몇개의 수를 정렬해야하는지 나타내는 수이고

그 다음부터가 정렬을 해야 할 숫자들이다

 

위의 수를 카운팅 정렬을 사용하면 다음과 같이 저장이 된다.

arr

0	1	2	3	4	5	6	7	8	...
0	2	2	2	1	2	0	1

5->arr[5]++

2->arr[2]++

3->arr[3]++

1->arr[1]++

4->arr[4]++

2->arr[2]++

3->arr[3]++

5->arr[5]++

1->arr[1]++

7->arr[7]++

 

주어진 예제에서

1은 총 두 번나오고

2와 3 그리고 5 역시도 총 두 번씩 나온다.

4와 7은 한 번씩 등장하므로 위와 같이 저장이 된다.

 

이제 반복문을 통해 맨 첫번째 i부터 순서대로 i를 element만큼씩 출력 해 주면 된다.

1

1

2

2

3

3

4

5

5

7