[10989] 수 정렬하기 3 (JAVA)

# 문제 설명

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

---

입력

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

---

출력

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

 

# 정답 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(st.nextToken()); //배열의 크기

        int[] A = new int[N];
        int max = 0;

        for (int n = 0; n < N; n++) {
            st = new StringTokenizer(br.readLine());
            A[n] = Integer.parseInt(st.nextToken());

            max = Math.max(max, A[n]);
        }

        int maxLength = 0;
        while (max != 0) {
            max /= 10;
            maxLength++;
        }

        radixSort(A, maxLength);

        for (int a : A) {
            sb.append(a + "\n");
        }

        System.out.print(sb);
    }

    public static void radixSort(int[] arr, int maxLength) {
        int[] output = new int[arr.length];
        int m = 1; //자릿수

        while (maxLength != 0) {
            int[] bucket = new int[10]; //0~9

            for (int a : arr) {
                bucket[(a / m) % 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] / m) % 10] - 1] = arr[i];
                bucket[(arr[i] / m) % 10]--;
            }

            for (int i = 0; i < output.length; i++) {
                arr[i] = output[i];
            }

            m *= 10;
            maxLength--;
        }
    }
}

 

기수 정렬을 이용하여 오름차순 정렬하였다.

메모리 제한이 있어 큐를 10개 만들면 메모리 초과가 된다.

따라서 누적합을 이용하였다.

 

정렬된 배열을 임시 저장할 output을 만든다.

현재 자릿수를 기준으로 데이터들을 나누어, 추가될 bucket에 1 증가한다.

 

bucket을 누적합 배열로 만들어 값이 들어갈 인덱스를 구하기 쉽도록 한다.

 

arr 배열의 끝부분부터 0까지 1씩 감소하면서 output에 데이터를 추가한다.

해당 bucket 수는 1 감소한다.

 

기존 배열 arr에 output을 옮겨주고, 자릿수를 바꾸고 maxLength를 1 감소한다.