[JAVA][Baekjoon] 10989번 수 정렬하기 3 🌟🌟🌟🌟🌟

https://www.acmicpc.net/problem/10989

 

📌 접근 방식

이 문제는 N의 최대 개수가 10,000,000으로 매우 크기 때문에 O(nlogn) 보다 더 빠른 알고리즘이 필요하다.

그렇기 때문에 기수 정렬을 사용해 풀어보았다.

[알고리즘] 기수 정렬(Radix Sort)이란?

 

 

✅ PASS CODE

import java.io.*;

public class Main {
    public static int[] arr;
    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());
        arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        radixSort(arr, 5);
        br.close();
        for (int i = 0; i < N; i++) {
            bw.write(arr[i] + "\n");
        }
        bw.flush();
        bw.close();
    }
    public static void radixSort(int []arr, int max_size) {
        int []output = new int[arr.length];
        int count = 0;
        int j = 1;
        while(count < max_size) {
            int []bucket = new int[10];
            for(int i=0; i<arr.length; i++) {
                bucket[((arr[i] / j) % 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] / j) % 10] - 1] = arr[i];
                bucket[(arr[i] / j) % 10] --;
            }
            for(int i=0; i<arr.length; i++) {
                arr[i] = output[i];
            }
            j *= 10;
            count ++;
        }
    }
}

📌 코드 분석

int []output = new int[arr.length];
int count = 0;
int j = 1;

• output : 정렬된 배열을 임시 저장하는 용도로 사용
• count : 현재 처리 중인 자릿수를 추적 (최대 max_size까지 반복)
• j : 자릿수를 나타내며, 처음에는 1의 자리를 처리

 

int []bucket = new int[10];
for (int i = 0; i < arr.length; i++) {
    bucket[((arr[i] / j) % 10)]++;
}

• bucket: 0부터 9까지 각 숫자의 개수를 저장하는 배열
• (arr[i] / j) % 10: 현재 자릿수의 값 추출
  • ex)
    123/1%10=3123 / 1 \% 10 = 3123/1%10=3 → 1의 자리 값
    123/10%10=2123 / 10 \% 10 = 2123/10%10=2 → 10의 자리 값
    123/100%10=1123 / 100 \% 10 = 1123/100%10=1 → 100의 자리 값

for (int i = 1; i < 10; i++) {
    bucket[i] += bucket[i - 1];
}

 

• 누적 빈도를 계산하여, 숫자가 배열 내에서 정렬될 최종 위치 결정
  • ex)
    bucket[2]=5 라면, 숫자 2는 결과 배열의 5번째 자리에 위치함
  • ex) 
    input : [170,45,75,90,802,24,2,66]
    bucket = [2, 0, 2, 0, 1, 2, 1, 0, 0, 0]
    누적 빈도 계산
    ➡️ bucket = [2, 2, 4, 4, 5, 7, 8, 8, 8, 8]
    

for (int i = arr.length - 1; i >= 0; i--) {
    output[bucket[(arr[i] / j) % 10] - 1] = arr[i];
    bucket[(arr[i] / j) % 10]--;
}

 

• 배열을 역순으로 순회하며 각 숫자를 output 배열의 적절한 위치에 삽입
• bucket 값을 감소시켜 다음 위치를 준비
  ➡️ 안정 정렬 보장

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

• 정렬된 output 배열의 값을 원래 배열 arr에 복사하여 업데이트

j *= 10;
count++;

• 다음 자릿수(10의 자리, 100의 자리 등)를 처리하기 위해 j를 10배로 늘림
• count를 증가시켜 반복 횟수 추적

 

 

 

💡 느낀 점

누적 빈도 계산과 역순으로 정렬하는 부분이 이해가 안가서 오래 걸렸다...

처음에는 왜 bucket 배열에 누적 빈도를 계산하는지, 왜 역순으로 결과 배열에 숫자를 넣는지 도통 이해를 못했다..

하지만 디버깅을 하면서 누적 빈도는 결과 배열에서 숫자의 정확한 위치를 계산하기 위해 필요하고, 역순 삽입은 안정 정렬을 보장하기 위한 중요한 과정임을 알게 되었다! 아마 다시 풀면 또 헷갈릴 수도 있다.. 여러번 풀어보고 익숙해져야지.. 🥹🔥