백준 10989 수 정렬하기 3

문제

풀이

public class Q10989_수정렬하기3 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        radix(arr, 5);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int i = 0; i < n; i++) {
            bw.write(arr[i] + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }

    public static void radix(int[] arr, int max) {
        // 각 자리수 계산하기 위한 변수
        int jarisu = 1;
        // 5자리수(10000)를 카운트 하는 변수
        int cnt = 0;
        // 각 자리수별로 정렬 결과를 임시로 저장할 변수
        int[] result = new int[arr.length];
        // 각 자리수 별로 정렬 진행
        while (cnt < 5) {
            // 각 자리수가 저장될 idx를 계산하기 위한 배열
            int[] bucket = new int[10];
            for (int i = 0; i < arr.length; i++) {
                // 각 자리수 데이터 개수 세기
                // 예를 들어 0의 자리 데이터가 12개, 1의 자리 데이터가 10개가 있다고 한다면
                bucket[(arr[i] / jarisu) % 10]++;
            }
            for (int i = 1; i < 10; i++) {
                // 각 자리수의 끝 idx부터 1씩 감소하며 저장하기 위해 합배열 사용
                // 예를 들어 0의 자리 데이터가 12개, 1의 자리 데이터가 10개가 있다고 한다면
                // bucket[0] = 12
                // bucket[1] = 22가 저장됨
                bucket[i] += bucket[i - 1];
            }
            for (int i = arr.length - 1; i >= 0; i--) {
                // 각 자리수마다 나뉜 구역의 끝 인덱스에 데이터를 저장
                result[bucket[(arr[i] / jarisu % 10)] - 1] = arr[i];
                // 다음 데이터를 위해 인덱스를 -1해줌
                // 예를 들어 1의자리 데이터(bucket[1])가 21번째 인덱스에 저장되었다면
                // 다음 1의자리 데이터(bucket[1])는 20번째 인덱스에 저장
                bucket[(arr[i] / jarisu % 10)]--;
            }
            for (int i = 0; i < arr.length; i++) {
                // 각 자리수의 정렬이 끝날때마다 원본 배열에 저장
                arr[i] = result[i];
            }
            // 다음 자리수 정렬을 위해 변수에 *10을 해준
            jarisu = jarisu * 10;
            // 정렬횟수 +1
            cnt++;
        }
    }
}

리뷰

분명히 백준 난이도는 브론즈1이었는데 왜 골드나 플래티넘급으로 어렵게 느껴지나 했다ㅜㅜ
다른 사람들의 풀이를 보니 sort메서드나 데이터의 범위인 10000길이의 배열을 선언하여 각 수별로 몇개가 나왔는지 개수를 누적하는 방식의 풀이로 엄청 간단하게 해결했다....

근데 나는 기수정렬을 이용해 풀이하는 방법을 익히다 보니 이렇게 오래걸렸다ㅜ

기수 정렬은 1의 자리 숫자로 먼저 정렬을 하고, 그 다음은 10, 그 다음은 100으로 각 자리수별로 정렬을 하는 방식으로 진행이 된다.

1. bucket이라는 배열을 이용해
   • 0~9까지 각 자리수별로 0데이터가 몇개인지, 1데이터가 몇개인지를 계산하고
   • 다시 합배열을 만들어 0부터 9까지의 각 데이터들의 범위를 구한다.
   • 예를 들어 0의 자리 데이터가 12개, 1의 자리 데이터가 10개가 있다고 한다.
     bucket[0] = 12로 인덱스 0~11에 데이터가 저장되어야 하고,
     bucket[1] = bucket[0] + 12 = 22로 인덱스 12~21에 데이터가 저장이 되어야 한다.
2. 이렇게 1의 자리 숫자를 기준으로 정렬이 완료되었다면, 다음 반복문을 통해 10의 자리수를 기준으로 정렬을 진행하고, 이 과정을 10000까지 진행한다.

문제 풀이를 하면서 너무 나는 너무 어렵게 느껴지는데 난이도는 브론즈1이라고 해서 이게 맞나? 싶었는데 다른 사람의 풀이를 보고 이해가 됐다. 시간은 오래 걸렸지만 새로운 알고리즘을 알게 됐다는 것으로 만족하자ㅜㅜ