[B1] 수 정렬하기 3 : Java : 10898 - 기수 정렬

문제

10989번: 수 정렬하기 3

 

 

 

 

접근 방법

수의 개수 제한은 천 만으로 많은 편에 속하지만 수의 크기는 만으로약 4자릿수가 최대. 이때는 자릿수에 따라 시간 복잡도 결정되는 기수 정렬이 좋은 방법.

 

기수 정렬

기수 정렬
값을 비교하지 않는 특이한 정렬으로 자릿수를 정한 다음 해당 자릿수만 비교한다. 
기수 정렬의 시간 복잡도는 O(kn)으로, 여기서 k는 데이터의 자릿수를말한다.

기수 정렬 알고리즘

• 10개(0~9)의 큐를 이용하여 값의 자릿수를 대표한다.
• 일의 자릿수부터 10개의 큐에 넣어가며 정렬을 한다. 
•  큐에 들어있는 모든 수를 0~9 순으로 꺼낸다. -> 해당 자릿수 정렬 완료.
• 마지막 자릿수를 기준으로 정렬할 때까지 앞의 과정을 반복한다.

 

 

 

코드 - Java

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


public class Main {

    public static int[] A;
    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 N = Integer.parseInt(br.readLine());
        A = new int[N];
        for(int i=0; i<N; i++){
            A[i] = Integer.parseInt(br.readLine());
        }
        br.close();
        Radix_Sort(A,5);
        for(int i=0; i<N; i++){
            bw.write(A[i]+"\n");
        }
        bw.flush();
        bw.close();
    }

    public static void Radix_Sort(int [] A, int max_size){
        int [] output = new int[A.length];
        int jarisu = 1;
        int count = 0;
        while(count != max_size){
            int[] bucket = new int[10];
            for(int i=0; i< A.length; i++){
                bucket[(A[i]/jarisu)%10]++;
            }
            for(int i=1; i< 10; i++){
                bucket[i] += bucket[i-1];
            }
            for(int i=A.length-1; i>=0; i--){
                output[bucket[A[i]/jarisu%10] -1] = A[i];
                bucket[(A[i]/jarisu)%10]--;
            }
            for(int i=0; i<A.length; i++){
                // 다음 자릿수를 이동하기 위해 현재 자릿수 기준 정렬 데이터 저장하기
                A[i] = output[i];
            }
            jarisu = jarisu*10;
            count++;
        }
    }

}