[백준 / 10989번] 수 정렬하기 3 - (Java - Counting Sort / 개수 정렬)

 

10989번: 수 정렬하기 3

---

 

⭐️ 코드

// 수 정렬하기 3

// Counting Sort - 개수 정렬
// 배열의 사이즈가 작고, 숫자의 범위가 10_000 이하일 때 사용 가능
// 배열에 입력된 동일한 숫자의 개수를 count 해서 배열이 0이 아닌것을
// 순서대로 count 수만큼 반복 출력하는 것

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

public class 수_정렬하기3 {
    private static final int MAX = 10_000;

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

        int N = Integer.parseInt(st.nextToken());

        int[] cnt = new int[MAX + 1];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            cnt[x]++;
        }

        for (int i = 0; i <= MAX; i++) { // O(K)
            for (int j = 0; j < cnt[i]; j++) {
                bw.write(i + "\n"); // O(N)
            }
        }
        bw.flush();
    }
}

---

💡 문제 풀이

Counting Sort

Sorting 알고리즘에는 여러 가지가 있는데 그중에서 Counting Sort(개수 정렬)을 이번 문제에서 사용할 예정이다.

Counting Sort는 문제에서 주어지는 수가 적을 때 Quick Sort보다 빠르게 정렬을 할 수 있는 방법이라고 한다.

 

Counting Sort의 알고리즘은 간단하다.

모든 나올 수 있는 숫자의 양에 대한 배열을 만들고 배열에 해당하는 index이자 '숫자'에 동일한 값이 출력될 때마다 하나씩 더해주는 것이다. 그 후 모든 배열을 탐색하여 순서대로 그 배열의 숫자 크기만큼 출력해 주면 된다.

 

// 입력 값
10
5
2
3
1
4
2
3
5
1
7

입력 값을 보게 되면 10개의 수를 입력받는다. 저 숫자들이 들어갈 수 있는 배열을 만들고 그 숫자들이 몇 번 추가되었는지 계산해 보면

아래와 같이 출력이 된다.

// 출력 값
1
1
2
2
3
3
4
5
5
7

---

👀 후기

Counting Sort 생각보다 단순하지만 알고리즘을 생각하기 까지가 조금 까다로운 것 같다..