수 정렬하기 3

백준10989번 수 정렬하기 3

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

소스

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

public class Main {
    static int N;
    static int[] input;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder result = new StringBuilder();
        N = Integer.parseInt(br.readLine()); //숫자 개수(문제 제시된 값)
        input = new int[N]; //입력받은 배열
        for(int i = 0; i < N; i++) {
            input[i] = Integer.parseInt(br.readLine());
        }

        radixSort(input);
        for(int i : input)
            result.append(i).append('\n');
        System.out.print(result);
    }

    static void radixSort(int[] input) {
        int[] bucket = new int[10]; //n자릿수가 몇 개 있는지 알려주는 합 배열
        int[] output = new int[N]; //임시 정렬 배열
        int now = 1; //현재 자릿수
        int cnt;
        while(now < 100000) {
            Arrays.fill(bucket, 0);
            Arrays.fill(output, 0); //0으로 초기화

            for (int i = 0; i < N; i++) {
                int num = input[i] % (now * 10) / now;
                bucket[num] += 1;
            }
            for (int num = 1; num < 10; num++) { //1부터 9까지
                bucket[num] += bucket[num - 1];
            }

            for (int i = N - 1; i >= 0; i--) {
                int num = input[i] % (now * 10) / now;
                int index = bucket[num] - 1;
                output[index] = input[i];
                bucket[num]--;
            }
            for(int i = 0; i < N; i++)
                input[i] = output[i];
            now *= 10;
        }
    }

}