[백준 - 10989] 수 정렬하기 3 .java

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

 

 

Solution

n의 최대 개수가 매우 크기 때문에 O(nlogn)보다 빠른 알고리즘을 이용해야한다.

문제에서 주어지는 숫자의 크기가 10,000보다는 작기 때문에 O(kn)의 시간복잡도인 기수 정렬을 사용했다.

다만, 문제 예시는 자리수가 여러개이지 않기 때문에 새로운 예시를 들어 풀었다.

 

 

 

 

각 해당 자리수의 숫자 = (전체 숫자 / 자릿수) % 10 
10으로 나눈 나머지가 0~9이기 때문

 

왜 합 배열을 구하는가?

합 배열을 구하는 이유는 각 숫자가 정렬된 배열에서 정확히 어느 위치에 들어가야 하는지를 알기 위해서!

각 자릿수 값의 위치를 누적 계산하여 알려주므로, 이를 통해 안정적으로 숫자들을 정렬된 배열에 배치 가능

• 각 자릿수 값의 끝 위치를 나타냄
• 배열을 역순으로 순회하면서 합 배열을 활용해 숫자를 배치하면, 동일한 자릿수 값의 상대적인 순서가 유지

 output 배열의 인덱스가 정렬된 후 해당 수가 몇 번째로 오는지
-> 하지만 0번째로 큰 수는 없기에 -1을 통해 인덱스 시작을 1로~

 

안정 정렬의 중요성

안정 정렬이란, 같은 값을 가진 요소들의 상대적인 순서가 정렬 후에도 유지되는 정렬

• 정렬된 결과에서 동일한 키를 가진 요소들이 입력 순서와 동일한 순서로 나열되도록 보장
• 자릿수별로 정렬을 반복하기 때문에 각 단계에서 안정성이 중요.
• 예를 들어, 십의 자리 정렬을 수행한 후 일의 자리를 정렬할 때, 십의 자리의 순서가 유지되어야 함.

역순으로 처리하는 이유

• 뒤에서부터 원소를 배치하면서 같은 값을 가진 원소들이 입력 순서대로 배치됨
• 즉, 같은 자릿수 값을 가진 원소들이 입력 순서를 유지하면서 배열에 배치
• 이 방식은 합 배열을 사용하여 각 원소의 정확한 위치를 계산할 때 유용
• => 합 배열을 기반으로 인덱스를 찾고, 배열을 역순으로 순회하면서 그 위치에 원소를 배치하면, 안정성이 보장

기수 정렬이 처음이라 중간중간 참고하려 코드를 봐도 이해가 전혀 되지 않아 손으로 일일이 예시를 풀었고

그 과정에서 이해한 부분을 코드 주석으로 나타내었다.

 

 

import java.io.*;

public class Main {
    public static int[] nums;

    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());
        nums = new int[n];

        // 배열 요소 입력
        for(int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(br.readLine());
        }
        
        // Radix Sort 수행, 자릿수 최대 5개 (10,000보다 작거나 같은 수)
        sort(nums, 5);

        // 정렬된 배열 출력
        for(int i = 0; i < n; i++) {
            bw.write(nums[i] + "\n");
        }
        bw.flush();
        bw.close();
    }

    public static void sort(int[] nums, int k) {
        // 임시 배열 선언
        int[] output = new int[nums.length];
        // 자릿수를 나타내는 변수 (1의 자리, 10의 자리, 100의 자리 등)
        int jari = 1;
        // 자릿수 처리 변수
        int count = 0;
        
        // 최대 k 자릿수까지 반복
        while(count != k) {
            // 버킷 배열 초기화 (각 자릿수 값의 개수)
            int[] bucket = new int[10];

            // 자릿수 값의 빈도수 계산
            for(int i = 0; i < nums.length; i++) {
                bucket[(nums[i] / jari) % 10]++;
            }
            
            // 누적 합 배열 계산 (해당 자릿수 값의 최종 위치 계산)
            for(int i = 1; i < 10; i++) {
                bucket[i] += bucket[i - 1];
            }

            // 현재 자릿수를 기준으로 배열 정렬
            for(int i = nums.length - 1; i >= 0; i--) {
                int digit = (nums[i] / jari) % 10;
                output[bucket[digit] - 1] = nums[i];
                bucket[digit]--;
            }

            // 다음 자릿수를 이동하기 위해 현재 자릿수 기준 정렬 데이터 저장
            for(int i = 0; i < nums.length; i++) {
                nums[i] = output[i];
            }

            // 자릿수 증가 (1 -> 10 -> 100 -> 1000 ...)
            jari *= 10;
            count++;
        }
    }
}