[알고리즘 공부] 자바를 통한 카운팅 정렬 구현 (백준 10989)

백준 10989번 문제를 풀던 중...
너무 간단하게 풀리는 문제 아닌가? 하고 냅다 Arrays.sort()를 사용했다.
결론: 시간 초과!

그렇다면 힙큐를 사용하는 것인가?
결론: 시간 초과였다.

서치를 해 본 결과 카운팅 정렬로 풀린다는 정보를 입수

아래는 해당 내용을 구현한 것이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 입력 가능한 수는 10000과 같거나 작은 자연수이다.
        int[] cnt = new int[10001];

        int N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
        	// 해당 index 값을 하나씩 올려 준다.
            cnt[Integer.parseInt(br.readLine())]++;
        }

        StringBuilder sb = new StringBuilder();

        for (int i = 1; i < 10001; i++) {
        	// 해당 인덱스 값이 0이 될 때까지 빼면서 StringBuilder에 추가해 준다.
            while (cnt[i] != 0) {
                sb.append(i).append("\n");
                cnt[i]--;
            }
        }
        System.out.println(sb);
    }
}

포용 가능한 크기의 배열을 미리 만들어 놓고 해당 인덱스의 카운트를 올리는 정렬 방식이다.
Arrays.sort()로 풀어도 가능하다는 말이 있는데... 그때는 StringBuilder를 사용하지 않고 냅다 for문을 돌려 System.out.println을 때려서 그런 듯

카운팅 정렬의 시간복잡도는 O(N + K)이다. K는 자릿수를 의미한다.