[24/12/5] 기수정렬

 

 

5초인데 천만개를 받고 자리수가 10000보다 작으니까 2^100보단 무조건 작다. 따라서 

O(nlogn)은 된다는건데... 그래서 Arrays.sort 하면 평균값 O(nlogn), 최악 O(n^2)이니까 이건 불확실하다. (O(n^2)을 저격하는 테케가 있으면 안되겠지...)

그러면 안전하게 풀려면 O(n)과 유사하게 풀어야된다는거같은데...

이러면 O(Kn)을 가지는 기수정렬을 써야한다.

 

큐에 넣어도 되지만 나는 그냥 bucket이라는 배열을 만들어놓고 각 끝자리에 맞게 index 맞춰서 넣었다.

중요한게 bucket에 넣고 이 순서대로 다시 빼고,

그 순서로 다시 bucket에 넣어서 다음 자리 기준으로 정렬한다.

이걸 최대 자리 수만큼 반복하면 된다.

 

문제는 이 과정에서 "합배열" 을 사용한다.

 

어떠한 배열을 카운팅 배열로 사용한다고 가정하자.

끝 자리에 따라 일의자리가 1이면 카운팅 배열 index 1에 카운팅해주고, 이것을 모든 배열 원소에 대해 반복한다.

 

 이 이후 카운팅 배열 순서대로 다시 기존 배열을 재배열할때 "합배열"을 사용한다.

 

기존 원소의 위치는 해당 원소가 합배열에서 카운팅된 index 위치에 있는 합배열 값의 -1이다.

예를 들면 

기존배열 
10 21 49 28 17 19 59 22 34

bucket 
10 21 22 34 17 28 49
                  19
                  59
                  
                 
카운팅 배열 
1  1  1  0  1  0  0  1  1  3

합배열
1  2  3  3  4  4  4  5  5  8

 

기존배열의 49는 카운팅배열대로 재배치했을때의 index가 49가 위치한 합배열 값의 -1 이다.

49를 위치시켜주고 해당 합배열 원소 값을 -1 해주면 다시 19가 이에 해당하는 합배열 값은 49보다 하나 바로 앞에 위치하게 된다.

 

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

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n =Integer.parseInt(st.nextToken());
        int max =0;
        int[] arr = new int[n];
        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            String iDigit = st.nextToken();
            int N = iDigit.toCharArray().length;
            if(N>max){
                max=N;
            }
            arr[i]= Integer.parseInt(iDigit);
        }
        int[] anw = radixSort(arr,max);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i=0; i<n; i++){
            bw.write(anw[i]+"\n");
        }
        bw.flush();
        bw.close();

    }
    public static int[] radixSort(int[] arr, int max){
        //bucket 0~9까지 넣고
        //bucket에서 빼서 재정렬
        //합 배열
        // 10 21 49 28 17 19 59 22 34
        // 10 21 22 34 17 28 49
        //                   19
        //                   59
        //  1  1  1  0  1 0 0 1 1 3
        //  1  2  3  3  4 4 4 5 5 8
        // 뒤부터 돌면서 temp =A[배열[i]%10]--
        // new배열[temp-1]
        // new 배열을 배열로 복사
        // 이걸 max 자릿수만큼 반복
        int l = 1;
        for(int i=0 ; i<max; i++){
            int[] bucket= new int[10];
            int[] newArr = new int[arr.length];
            for(int j=0; j<arr.length; j++){ //n번
                bucket[arr[j]/l%10]++;
            }
            for(int j=1; j<10; j++){  //10번
                bucket[j]+=bucket[j-1];
            }
            for(int j=arr.length-1; j>=0; j--){ //n번
                int temp = bucket[arr[j]/l%10]--;
                newArr[temp-1]=arr[j];
            }
            for(int j=0; j<arr.length; j++){ //n번
                arr[j]=newArr[j];
            }
            l=l*10;
        }
        return arr;
    }
}

 

보면 Arrays.sort() 와 빠른 입출력을 위한 BufferedReader , BufferedWriter 쓰면 통과된다고는 한다. 최악의 상황이 나와 O(n^2) 이 걸리는게 없어서 통과는 되지만 기수정렬을 알 수 있는 문제였다.

 

물론 Collections.sort 처럼 평균.최악 모두 O(nlogn)를 써도 된다.