[알고리즘] Java로 배우는 카운팅 정렬 - feat.백준(수 정렬하기3)

 

이 문제는 주어진 N개의 수를 오름차순으로 정렬해야 한다. 수의 개수(N)가 최대 10,000,000이지만, 주어진 값이 10,000 이하의 자연수로 한정적이라는 점에서 카운팅 정렬(Counting Sort)을 사용할 수 있다. 카운팅 정렬은 정수 데이터의 범위가 제한되어 있을 때 매우 효율적인 알고리즘이다.

카운팅 정렬의 시간 복잡도는 O(N+K)이며 K는 값의 범위이다. 따라서 입력 크기가 크더라도 효율적으로 정리할 수 있다.

 

 

• N = 10
• 입력: 5, 2, 3, 1, 4, 2 ,3 ,5, 1, 7

 

카운트 배열 생성

데이터의 범위가 1~10,000이므로 크기가 10,0001인 카운트 배열을 생성한다. 입력된 값의 등장 횟수를 카운트 배열에 저장한다.

 

카운팅 정렬에서는 값의 크기를 인덱스로 사용한다. 

예를 들면, 처음 num에 들어올 값은 5이고 count[5]의 값을 하나 증가시킨다. 그 다음은 count[2]의 값 증가, 그 다음은 count[3]의 값을 증가시킨다. 8번째 입력을 받았을 때 다시 count[5]의 값이 증가한다.

int n = Integer.valueOf(br.readLine());
int[] count = new int[10001];
for (int i = 0; i < n; i++) {
    int num = Integer.valueOf(br.readLine());
    count[num]++;
}

 

 

 

정렬된 결과 출력

카운트 배열의 각 인덱스를 반복하며 등장 횟수만큼 출력한다.

count[i]가 0 초과라면 그 숫자를 출력하고 0이라면 출력없이 다음으로 넘어간다.

for (int i = 0; i <= 10000; i++) {
    while (count[i] > 0) {
        bw.write(i + "\n");
        count[i]--;
    }
}

 

숫자 (인덱스)	1	2	3	4	5	6	7	...
등장 횟수	2	2	2	1	2	0	1	...

 

count[1] = 2, 값 1이 2번 등장했다는 의미가 되며 출력은 1, 1이 된다.

count[2] = 2, 값 2가 2번 등장했다는 의미가 되며 출력은 2, 2가 된다. (1, 1, 2 ,2)

count[3] = 2, 값 3이 2번 등장했다는 의미가 되며 출력은 3, 3이 된다. (1, 1, 2, 2, 3, 3)

count[4] = 1, 값 4가 1번 등장했다는 의미가 되며 출력은 4가 된다. (1, 1, 2, 2, 3, 3, 4)

count[5] = 2, 값 5가 2번 등장했다는 의미가 되며 출력은 5, 5가 된다. (1, 1, 2, 2, 3, 3, 4, 5, 5)

count[6] = 0, 값 6이 0번 등장했다는 의미가 되며 출력이 없다.

count[7] = 1, 값 7이 1번 등장했다는 의미가 되며 출력은 7이 된다. (1, 1, 2, 2, 3, 3, 4, 5, 5, 7)

그 이후는 모두 0이므로 출력이 없다.

 

 

전체 코드

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

public class Main {
    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.valueOf(br.readLine());
        int[] count = new int[10001];
        for (int i = 0; i < n; i++) {
            int num = Integer.valueOf(br.readLine());
            count[num]++;
        }
        for (int i = 0; i <= 10000; i++) {
            while (count[i] > 0) {
                bw.write(i + "\n");
                count[i]--;
            }
        }
        bw.flush();
        bw.close();
    }
}