백준 10989번 수 정렬하기 3 - 계수 정렬

문제 설명

자연수 N개가 주어진다. 이 수들을 오름차순으로 정렬해서 한 줄에 하나씩 출력하는 문제이다.

시간 초과에 유의해야 한다.

---

입력 조건

• 첫째 줄에 N (1 ≤ N ≤ 10,000,000)
• 둘째 줄부터 N개의 줄에 정수 (1 ≤ 수 ≤ 10,000)

예제 입력

10
5
2
3
1
4
2
3
5
1
7

예제 출력

1
1
2
2
3
3
4
5
5
7

---

전체 코드

import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int n = Integer.parseInt(br.readLine());
		int[] count = new int[10001]; // 수의 범위: 1 ~ 10000

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

		for (int i = 1; i <= 10000; i++) {
			while (count[i]-- > 0) {
				sb.append(i).append('\n');
			}
		}

		System.out.print(sb);
	}
}

---

코드 설명

1. 입력 최적화: BufferedReader

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

• Scanner보다 훨씬 빠른 입력 처리 방식
• 1천만 개의 수를 받아야 하므로 필수

---

2. 계수 정렬: int[] count

int[] count = new int[10001];

• 각 숫자가 몇 번 나왔는지 세는 배열
• 수의 범위가 1~10,000이므로 배열 크기를 10001로 설정

---

3. 출력 최적화: StringBuilder

StringBuilder sb = new StringBuilder();

• System.out.println()을 수백만 번 호출하면 매우 느리다
• 출력값을 StringBuilder에 모아서 한 번에 출력

---

4. 정렬된 결과 출력

for (int i = 1; i <= 10000; i++) {
	while (count[i]-- > 0) {
		sb.append(i).append('\n');
	}
}

• count[i]가 0보다 클 동안 숫자 i를 출력