[백준 10989] 수 정렬하기 3 (Java)

🚀 문제 분석

• 데이터 개수 ($N$): 10,000,000 (천만 개)
• 시간 제한: 5초 (넉넉함)
• 메모리 제한: Java 기준 512MB (C++은 8MB로 극악이나, Java는 넉넉한 편)
• 핵심: $N$이 매우 크기 때문에 일반적인 $O(N \log N)$ 정렬보다 더 빠른 $O(kN)$ 정렬 알고리즘이 효율적입니다.

💡 왜 기수 정렬(Radix Sort)인가?

보통 이 문제는 범위가 좁아 계수 정렬(Counting Sort)로 풀지만, 저는 실무 활용도와 알고리즘 연습을 위해 기수 정렬을 선택했습니다.

기수 정렬의 장점

1. 안정 정렬(Stable Sort): 낮은 자릿수부터 정렬하며 동일한 값의 상대적 순서를 보장합니다.
2. 비교 연산 없음: 값의 크기를 직접 비교하지 않고 자릿수(Digit)별로 분포시키기 때문에 $O(N)$에 가까운 성능을 냅니다.
3. 확장성: 숫자의 범위가 더 커지더라도 자릿수($k$)만큼만 반복하면 되므로 대규모 데이터 처리에 유리합니다.

🛠️ 구현 디테일: LSD(Least Significant Digit) 방식

가장 낮은 자릿수(1의 자리)부터 가장 높은 자릿수(10,000의 자리)까지 총 5번의 패스를 거치며 정렬합니다. 각 패스 내부에서는 계수 정렬(Counting Sort) 로직을 활용하여 해당 자릿수를 기준으로 정렬을 수행합니다.

💻 최종 구현 코드 (Java)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws Exception {
        int N = nextInt();

        // 10,000,000개의 데이터를 담을 배열 (약 40MB)
        int[] nums = new int[N];
        for (int i = 0; i < N; i++) {
            nums[i] = nextInt();
        }

        // 기수 정렬 수행
        radixSort(nums);

        // 출력 최적화
        StringBuilder sb = new StringBuilder();
        for (int n : nums) {
            sb.append(n).append("\n");
        }
        System.out.print(sb);
    }

    static void radixSort(int[] arr) {
        int n = arr.length;
        int[] temp = new int[n]; // 정렬 결과를 임시 저장할 배열

        // 문제 조건: 숫자는 10,000보다 작거나 같은 자연수
        // 1의 자리(1)부터 10,000의 자리(10000)까지 10배씩 증가하며 반복
        for (int divisor = 1; divisor <= 10000; divisor *= 10) {
            int[] count = new int[10]; // 0~9 자릿수 카운팅

            // 1. 현재 자릿수 기준 빈도수 계산
            for (int i = 0; i < n; i++) {
                count[(arr[i] / divisor) % 10]++;
            }

            // 2. 누적합 계산 (Stable 정렬을 위한 인덱스 확보)
            for (int i = 1; i < 10; i++) {
                count[i] += count[i - 1];
            }

            // 3. 뒤에서부터 순회하며 temp 배열에 배치 (안정성 유지)
            for (int i = n - 1; i >= 0; i--) {
                int digit = (arr[i] / divisor) % 10;
                temp[count[digit] - 1] = arr[i];
                count[digit]--;
            }

            // 4. 현재 자릿수 정렬 결과를 원본 배열에 복사
            System.arraycopy(temp, 0, arr, 0, n);
        }
    }

    static int nextInt() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(br.readLine());
        }
        return Integer.parseInt(st.nextToken());
    }
}

🧐 기술적 고찰

• 공간 복잡도: 입력 배열($O(N)$)과 임시 배열($O(N)$)이 모두 필요합니다. Java의 512MB 제한 덕분에 가능했지만, 메모리가 극도로 제한된 환경(예: C++ 8MB)이라면 데이터를 아예 배열에 담지 않는 Counting Sort 전용 방식을 써야 했을 것입니다.
• 연습의 의미: 지난주에 다뤘던 병합 정렬($O(N \log N)$)에 이어, 데이터의 특성을 활용해 선형 시간($O(N)$)에 정렬하는 기수 정렬을 직접 구현해 봄으로써 정렬 알고리즘의 스펙트럼을 넓힐 수 있었습니다.