[백준] 10989 수 정렬하기 3

1. 문제 설명

문제링크

2. 접근 방식

기수 정렬을 이용해서 문제를 풀려고 했다. 근데, 다른 사람들의 질문을 보니, 예전에는 기수 정렬을 이용해 문제가 풀렸으나, 메모리 제한이 생긴 이후로 풀리지 않는다고 한다. 문제에서 주어지는 데이터의 크기는 10,000,000 개이고, 하나의 데이터를 int 배열의 원소로 넣어서 보관한다면, 총 40MB가 든다. (밑에 보면, java의 경우 512MB까지 용량 허용된다고 적혀있는데, 똑같이 안된다.)
기수 정렬의 공간 복잡도는 O(W+n)으로 40MB의 경우 문제에서 주는 메모리 용량을 초과한다. 내가 ArrayDeque 10개를 활용해 기수 정렬을 구현하는 바람에 오류가 났나 싶어서, 코딩 테스트 책에 있는 풀이를 똑같이 구현하였으나, 그건 또 시간초과가 났다.

하지만 그냥 기수정렬로 문제를 풀어보겠다. 여기 아니면 써볼 일이 없을 것 같다. 기수정렬은 최악의 시간복잡도가 O(kn) (k는 입력값 최대 자릿수)으로 지금까지 배운 정렬 중에서 가장 빠르지만, 10개의 Queue 혹은 그에 상응하는 bucket 배열을 따로 두어야 하기 때문에 메모리 소모가 엄청난 알고리즘이다.
해당 문제에서도 메모리 허용량이 8MB 이지만, 만약에 Bucket 배열을 int 배열로 만들 경우, 모든 데이터를 일일히 저장하기만 해도 40MB가 든다.
또한 데이터의 양/음 값에 상관없이 쓸 수 있었던 타 정렬에 비해 기수 정렬은 양의 정수는 양의 정수 끼리, 음의 정수는 음의 정수끼리 따로 정렬해서 값을 구해야하는 방식이다.

등가교환의 법칙에 따라 속도는 빠르지만, 조건이 까다롭고, 다른 정렬에 비해 공간복잡도가 많이 들어서 코테에서 자주 사용하는 방법이 아닌거 같다. 하지만 만약에 코테에서 메모리 제한이 512MB 이상으로 여유롭고, 데이터의 크기가 10^7 정도라면 사용해볼만 한 것 같다.

접근 방식

(1) String.charAt으로 현재 자릿수의 값을 특정한다. 만약 우리가 10000의 자릿수를 보고 있는데, 숫자가 12로 10의 자리까지 밖에 없다면 0으로 특정되도록 한다.

(2) 현재 자릿수의 값에 해당하는 ArrayDeque에 값을 집어넣는다.

(3) 0번 Deque부터 9번 Deque까지 차례대로 원래의 배열에 값을 집어넣는다.

(4) 해당 행위를 입력값 중 최대 자릿수 개수 만큼 반복한다. (ex- 자릿수의 개수가 5개면 5번 반복)

3. 코드 분석

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


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int max = 0;
        int N = Integer.parseInt(br.readLine());
        int [] arr = new int [N];
        ArrayDeque<Integer> [] aqs = new ArrayDeque[10];

        for (int i = 0; i < 10; i++) {
            aqs[i] = new ArrayDeque<>();
        }
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            max = Math.max(max, arr[i]);
        }

        int max_length = String.valueOf(max).length();
        int digit = 1;
        while (digit <= max_length){
            // 값 집어넣기
            for (int i = 0; i < N; i++) {
                String now = String.valueOf(arr[i]);
                if(now.length()>=digit) aqs[Character.getNumericValue(now.charAt(now.length()-digit))].add(Integer.parseInt(now));
                else aqs[0].add(Integer.parseInt(now));
            }
            // 값 재정렬해서 arr로 넣기
            int aqs_idx = 0;
            int arr_idx = 0;
            while (aqs_idx <= 9){
                while (!aqs[aqs_idx].isEmpty()){
                    arr[arr_idx++] = aqs[aqs_idx].poll();
                }
                aqs_idx++;
            }
            digit++;
        }

        // 출력
        for (int ans : arr){
            System.out.println(ans);
        }
    }
}

4. 성장하기

위에서는 기수 정렬을 이론 그대로 Queue를 10개 구현해서 문제를 풀었는데, 배열을 이용해, Queue 선언에 드는 불필요한 시간 소모를 줄이는 방법도 있어, 해당 방법을 공부 후에 기술한다.

bucket이란 배열을 만들어 해당 배열을 누적 합 배열로 사용하여 문제를 푼다.

• 첫 번째 계산
  bucket 배열의 index는 10개의 queue처럼 자릿수의 값을 의미한다. value는 해당 자릿수의 값을 가진 원소의 개수이다.
  (ex- 만약 현재 계산하는 수가 12345이고 보는 자릿수가 10이라면, bucket[4]++을 해줘야 한다.)

• 두 번째 계산
  누적합을 통해, 본 배열에 해당 값들이 들어갈 위치를 구한다. 예를 들어
  첫 번째 계산으로 만들어진 bucket 배열이 다음과 같다고 하자.

  1	2	3	4	5
  1	1	0	2	1

  현재 10의 자릿수를 보고 있다고 할 때 이것의 뜻은 10의 자릿수가 1인 값이 1개, 2인 값이 1개, 4인 값이 2개, 5인 값이 1개이다.
  이를 누적합을 바꿔보자

  1	2	3	4	5
  1	2	2	4	5

  이제 해당 값의 의미는 다음과 같다. index 5의 value == 5 인데, 10의 자릿수가 5인 값의 본 배열 arr 속 위치는 arr[5]라는 것이다.
  10의 자릿수가 4인 값이 2개 있었는데, 이건 어떻게 하나요?

  arr[4]에 값을 집어넣은 다음 bucket[4]-- 해서 인덱스를 한 칸 줄인다.

🕹️숫자의 특정 자릿수에 해당하는 값을 구하는 방법 🕹️

int n = 12345; 
int digit = 100; // 구하려는 특정 자릿수 

System.out.println((n/digit)%10);
/*
    1. n/digit으로 원본 값에서 원하는 자릿수 이하의 값들을 모두 잘라낸다.
       (이렇게 되면 구하고자 하는 자릿수의 값이 1의 자릿수가 될 것이다.)
    2. %10 계산으로 구하고자 하는 값만 따로 떼어낸다.
*/

전체 코드

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


public class Main {
    public static int[] A;

    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 cnt = 0;
        int digit = 1;
        while (cnt <= max_size){
            // bucket은 누적합 배열이 되기 전까지는 index = 자릿수, value = 해당 자릿수의 값의 개수 이다.
            // 예를 들어 bucket[4]는 현재 자릿수 = 4인 값의 개수이다.
            // 누적합이 되면, bucket의 index는 그 index에 해당하는 자릿수를 가진 값이 본 배열 A에 저장될 때 위치이다.
            // 예를 들어 bucket[4] = 4 이고 자릿수는 10이라고 해보자 . 그러면 12345라는 숫자는 본 배열 4번째 자리에 저장된다.
            // 만약 2345라는 숫자가 하나 더 있어서 자릿수가 겹치는 경우는 어떻게 할까 이 경우 bucket[4]는 아까 4번쨰 자리에 값 하나를
            // 저장 했음으로, 3이 될 것이고 2345는 본 배열 A의 3번쨰 자리에 저장된다.
            int [] bucket = new int [10];

            for (int i = 0; i < A.length; i++) {
                bucket[(A[i]/digit)%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]/digit)%10]-1] = A[i];
                bucket[(A[i]/digit%10)]--; // -> 보면 배열을 뒤에서뷰토 채우고 있다.
                                        // -> 따라서 나중에 10000으로 나누었을 시 많은 수들이 0에 저장되어 있을텐데,
                                            // 큰 인덱스를 작은 값부터 채우면 내림차순이 될 수 밖에 없다.
            }

            for (int i = 0; i < A.length; i++) {
                A[i] = output[i];
            }
            digit *= 10;
            cnt++;
        }
    }
}