[Java] 10989 수 정렬하기 3

문제

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

 

입력

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

 

출력

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

 

import java.util.*;
import java.io.*;

public class Main{
    public static int[] arr;
    public static long result;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int num = Integer.parseInt(br.readLine());
        arr = new int[num];
        
        for(int i=0; i<num; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }
        br.close();
        Radix_Sort(arr, 5);
        
        for(int i=0; i<num; i++){
            bw.write(arr[i] + "\n");
        }
        bw.flush();
        bw.close();
    }
    
    public static void Radix_Sort(int[] arr, int max_size){
        int[] output = new int[arr.length];
        int jarisu = 1;
        int count = 0;
        
        while(count != max_size){
            int[] bucket = new int[10];
            for(int i=0; i<arr.length; i++){
                bucket[(arr[i] / jarisu) % 10]++;
            }
            for(int i=1; i<10; i++){
                bucket[i] += bucket[i-1];
            }
            for(int i=arr.length-1; i>=0; i--){
                output[bucket[(arr[i] / jarisu % 10)] - 1] = arr[i];
                bucket[(arr[i] / jarisu) % 10]--;
            }
            for(int i=0; i<arr.length; i++){
                arr[i] = output[i];
            }
            jarisu *= 10;
            count++;
        }
    }
}