[백준] 수 정렬하기 3

수 정렬하기 3

주어진 N개의 수를 오름차순으로 정렬하는 문제를 해결합니다. 주어진 수는 10,000보다 작거나 같은 자연수로, 입력값의 범위가 크기 때문에 효율적인 정렬 알고리즘이 필요합니다.

문제 조건

• N개의 수가 주어짐 (1 ≤ N ≤ 10,000,000)
• 주어진 수는 10,000보다 작거나 같은 자연수
• 오름차순으로 정렬한 결과를 출력
• 시간 제한: 5초
• 메모리 제한: 8MB
• 문제 링크

10989번: 수 정렬하기 3

주요 개념

• 계수 정렬(Counting Sort) 알고리즘 사용
• 입력과 출력의 효율을 위해 BufferedReader와 BufferedWriter 사용
• cnt 배열을 사용하여 1부터 10000까지의 자연수 각각이 몇 번 입력되었는지 저장

코드 설명

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

public class SortNumbers3 {
    public static void main(String[] args) throws IOException {
        // 입력과 출력을 위한 BufferedReader와 BufferedWriter 준비
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // N 입력 받기
        int N = Integer.parseInt(br.readLine());

        // 숫자의 개수를 저장할 배열 생성, 인덱스는 숫자를 의미하고 값은 개수를 의미
        int[] cnt = new int[10001];

        // N번 반복하며 숫자의 개수 기록
        for (int i = 0; i < N; i++) {
            cnt[Integer.parseInt(br.readLine())]++;
        }

        // 각 숫자에 대해 개수만큼 출력
        for (int i = 1; i <= 10000; i++) {
            while (cnt[i]-- > 0) {
                bw.write(i + "\n");
            }
        }

        // 남아있는 데이터 출력을 위해 버퍼 플러시
        bw.flush();
    }
}