[코딩테스트] 백준 10989 자바

백준 10989

백준 10989 문제

해당 문제는 n의 최대 개수가 10,000,000으로 매우 크기 때문에 O(n log n)보다 더 빠른 알고리즘이 필요하다. 문제에서 주어지는 숫자의 크기가 10,000보다 작다는 것을 바탕으로 O(kn)의 시간 복잡도의 기수 정렬을 사용하면 된다.

import java.io.*;

public class Boj10989 {

    private 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++) { // n의 개수만큼 반복
            arr[i] = Integer.parseInt(br.readLine()); // arr 배열 저장
        }

        br.close();

        radixSort(arr, 5); // 기수 정렬 메서드 수행

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

        bw.flush();
        bw.close();
    }

    private static void radixSort(int[] arr, int maxSize) {
        int[] output = new int[arr.length]; // 임시 정렬을 위한 배열
        int digit = 1; // 현재 자릿수를 표현하는 수
        int count = 0;

        while (count != maxSize) { // 최대 자릿수만큼 반복하기
            int[] bucket = new int[10]; // 현재 자릿수들의 분포를 합 배열의 형태로 알려 주는 배열

            // 현재 기준 자릿수를 기준으로 arr 배열 데이터를 bucket에 count
            for (int i = 0; i < arr.length; i++) {
                bucket[(arr[i] / digit) % 10]++; // 일의 자리부터 시작
            }

            // 합 배열 공식으로 bucket을 합 배열 형태로 변경
            for (int i = 1; i < 10; i++) { // 합 배열을 이용해 index 계산
                bucket[i] += bucket[i - 1];
            }

            for (int i = arr.length - 1; i >= 0; i--) { // n - 1에서 0까지 감소하면서 반복문 실행
                output[bucket[(arr[i] / digit % 10)] - 1] = arr[i]; // bucket값을 이용해 현재 기준 자릿수로 데이터를 정렬, output 배열에 저장하기
                bucket[(arr[i] / digit) % 10]--;
            }

            for (int i = 0; i < arr.length; i++) { // n의 개수만큼 반복
                arr[i] = output[i]; // 다음 자릿수 이동을 위해 arr 배열에 output 데이터 저장
            }

            digit = digit * 10; // 자릿수 증가
            count++;
        }
    }
}

1. 정렬할 수 개수를 n에 저장한다.
2. n만큼의 정렬할 배열을 선언한다.
3. n만큼 반복하며 arr 배열에 정렬할 수를 저장한다.
4. 기수 정렬 메서드 radixSort()를 호출하여 기수 정렬을 실행한다.
5. 임시 정렬을 위한 배열 output을 선언한다.
6. 현재 자릿수를 표현하는 digit를 일의 자리부터 시작하기 때문에1로 선언한다.
7. 최대 자리수를 넘지 않기 위해 count변수로 현재 자릿수를 저장하도록 한다.
8. 최대 자릿수만큼 반복하면서 현재 자릿수들의 분포를 합 배열의 형태로 알려 주는 배열 bucket을 선언한다.
9. 현재 기준 자릿수를 기준으로 arr 배열 데이터의 나머지에 맞는 인덱스에 카운팅해준다.
10. 현재 기준 자릿수를 기준으로 수의 위치(인덱스)를 계산하기 위해 합 배열 형태로 변경한다.
11. 배열의 끝에서부터 내려오면서 임시 정렬 배열 output에 합 배열로 계산된 정렬된 위치(인덱스)에 맞춰 수를 저장한다.
12. 자릿수 digit와 현재 자릿수 count를 증가시키면서 최대 자리수만큼 반복해준다.