[알고리즘/백준] 10989 수 정렬하기3(자바, 카운팅 정렬, Counting Sort)

문제

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

풀이 코드

퀵정렬을 사용하는 Arrays.sort()와 System.out.println() 메서드를 사용해서 풀이하면 시간 초과로 통과할 수 없고, 카운팅 정렬 + StringBuilder() 조합으로 풀이해야 통과할 수 있다.

카운팅 정렬에 관한 내용은 아래의 글을 참고하였고, 이번 문제 풀이를 통해 카운팅 정렬을 접해볼 수 있었다.
https://st-lab.tistory.com/104

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));
        int n = Integer.parseInt(br.readLine());

        //배열의 인덱스는 숫자, 배열의 값은 해당 숫자의 빈도수
        int[] count = new int[10001];

        //카운팅 정렬
        for (int i = 0; i < n; i++) {
            count[Integer.parseInt(br.readLine())]++;
        }

        StringBuilder sb = new StringBuilder();

        //오름차순으로 출력
        for (int i = 1; i <= 10000; i++) {
            for (int j = 0; j < count[i]; j++) {
                sb.append(i).append("\n");
            }
        }

        System.out.println(sb);
    }
}