[백준 10989] Counting Sort (계수 정렬) 알고리즘

✨ 문제

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

n개의 수를 입력받아 오름차순으로 정렬하여 출력하는 문제이다.

배열에 입력받은 수를 저장하고 Arrays.sort를 사용하여 정렬 후 출력하니 시간초과가 떠서

방법을 찾아보던 중 Counting Sort 알고리즘을 알게 되었다.

 

 

 

✨Counting Sort (계수 정렬) 알고리즘

- 정렬 알고리즘 중 하나로, 데이터 간의 비교를 하지 않고, 각 데이터의 빈도수를 이용해 정렬한다.

- 정수 데이터의 값의 범위가 제한적일 떄 매우 효율적이다.

- 동작 방식

1. 카운트 배열 초기화
   데이터가 가질 수 있는 최대값(k)에 따라 크기가 k + 1인 카운트 배열을 생성한다.
   각 인덱스는 데이터의 특정 값을 나타내고, 해당 인덱스의 값은 데이터에서 그 값이 몇 번 나타났는지를 저장한다
2. 빈도수 기록
   각 데이터 값에 해당하는 카운트 배열의 인덱스를 1씩 증가시킨다. 각 값의 등장 횟수를 카운트 배열에 저장하는 과정이다.
3. 정렬된 데이터 재구성
   카운트 배열을 순회하며 인덱스에 저장된 값을 바탕으로 원본 배열에 정렬된 데이터를 채운다. 인덱스를 해당 값이 나타난 횟수만큼 반복하여 출력하거나 새로운 배열에 추가하는 방식이다.

- 시간 복잡도 : O(n + k), 공간 복잡도 : O(n). (n : 배열 크기, k : 데이터 범위의 최대값)

- 데이터 값의 범위가 작고 데이터의 양이 많을 떄 유리하며, 간단하고 구현이 용이하다는 장점이 있다.

- 데이터 범위에 따라 메모리 사용량이 커질 수 있다는 단점이 있다.

 

 

 

✨ 코드

import java.io.*;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        int[] count = new int[10001];
        
        for (int i = 0; i < n; i++)
            count[Integer.parseInt(br.readLine())]++;

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