[10989] 수 정렬하기 3

✔ 수 정렬하기 3

[백준 10989]

문제 분석하기

N의 최대 개수가 10000000으로 매우 크기 때문에 O(nlogn) 보다 더 빠른 알고리즘을 사용해야 하므로

시간 복잡도가 O(kn)인 기수 정렬을 사용하여 문제에 접근하며 구간 합을 이용하여 구현

손으로 풀어보기

1. 자릿수가 서로 다른 경우 자릿수가 적은 수 앞에 0이 채워져 있다고 생각하여 큐에 삽입
2. 일의 자릿수를 기준으로 큐에 삽입 후 큐에서 순서대로 pop
3. 십의 자릿수를 기준으로 큐에 삽입 후 큐에서 순서대로 pop
4. 백의 자릿수를 기준으로 큐에 삽입 후 큐에서 순서대로 pop
5. 마지막 자릿수를 기준으로 정렬할 때까지 반복

예)  A = [5, 2, 3, 1, 4, 2, 3, 5, 1, 7]

jarisu	output	bucket
1	[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]	0 0	1 2	2 2	3 2	4 1	5 2	6 0	7 1	8 0	9 0
		0 0	1 2 (2+0)	2 4 (2+2)	3 6 (2+4)	4 7 (1+7)	5 9 (2+7)	6 9 (0+9)	7 10 (1+9)	8 10 (0+10)	9 10 (0+10)
	ouput[bucket[7 / 1 % 10] - 1] output[10 - 9] = output[9] = 7 [0, 0, 0, 0, 0, 0, 0, 0, 0, 7]	0 0	1 2	2 4	3 6	4 7	5 9	6 9	7 9 (10-1)	8 10	9 10
	ouput[bucket[1 / 1 % 10] - 1] output[2 - 1] = output[1] = 1 [0, 1, 0, 0, 0, 0, 0, 0, 0, 7]	0 0	1 1 (2-1)	2 4	3 6	4 7	5 9	6 9	7 9	8 10	9 10
	ouput[bucket[5 / 1 % 10] - 1] output[9 - 1] = output[8] = 5 [0, 1, 0, 0, 0, 0, 0, 0, 5, 7]	0 0	1 1	2 4	3 6	4 7	5 8 (9-1)	6 9	7 9	8 10	9 10
	ouput[bucket[3 / 1 % 10] - 1] output[6 - 1] = output[5] = 3 [0, 1, 0, 0, 0, 3, 0, 0, 5, 7]	0 0	1 1	2 4	3 5 (6-1)	4 7	5 8	6 9	7 9	8 10	9 10
	ouput[bucket[2 / 1 % 10] - 1] output[4 - 1] = output[3] = 2 [0, 1, 0, 2, 0, 3, 0, 0, 5, 7]	0 0	1 1	2 3 (4-1)	3 5	4 7	5 8	6 9	7 9	8 10	9 10
	ouput[bucket[4 / 1 % 10] - 1] output[7 - 1] = output[6] = 4 [0, 1, 0, 2, 0, 3, 4, 0, 5, 7]	0 0	1 1	2 3	3 5	4 6 (7-1)	5 8	6 9	7 9	8 10	9 10
	ouput[bucket[1 / 1 % 10] - 1] output[1 - 1] = output[0] = 1 [1, 1, 0, 2, 0, 3, 4, 0, 5, 7]	0 0	1 0 (1-1)	2 3	3 5	4 6	5 8	6 9	7 9	8 10	9 10
	ouput[bucket[3 / 1 % 10] - 1] output[5 - 1] = output[4] = 3 [1, 1, 0, 2, 3, 3, 4, 0, 5, 7]	0 0	1 0	2 3	3 4 (5-1)	4 6	5 8	6 9	7 9	8 10	9 10
	ouput[bucket[2 / 1 % 10] - 1] output[3 - 1] = output[2] = 2 [1, 1, 2, 2, 3, 3, 4, 0, 5, 7]	0 0	1 0	2 2 (3-1)	3 4	4 6	5 8	6 9	7 9	8 10	9 10
	ouput[bucket[5 / 1 % 10] - 1] output[8 - 1] = output[7] = 5 [1, 1, 2, 2, 3, 3, 4, 5, 5, 7]	0 0	1 0	2 2	3 4	4 6	5 7 (8-1)	6 9	7 9	8 10	9 10

슈도코드 작성하기

N(정렬할 수 개수)
A(정렬할 배열 선언하기)
for(N의 개수만큼 반복하기) {
    A 배열 저장하기
}
기수 정렬 함수 수행하기
정렬된 A 배열 출력하기

bucket(현재 자릿수들의 분포를 합 배열의 형태로 알려 주는 배열)
ex: bucket[4] -> 현재 기준 자릿값이 0 ~ 4까지 몇 개의 데이터가 있는지 저장하기
output(임시 정렬을 위한 배열)
jarisu(현재 자릿수를 표현하는 수)
while(최대 자릿수만큼 반복하기) {
    현재 기준 자릿수를 기준으로 A 배열 데이터를 bucket에 count
    합 배열 공식으로 bucket을 합 배열 형태로 변경하기
    for(i가 N-1에서 0까지 감소하면서 반복문 실행) {
        bucket값을 이용해 현재 기준 자릿수로 데이터를 정렬하기
        output 배열에 저장하기
    }
    for(N의 개수만큼 반복하기) {
        다음 자릿수 이동을 위해 A 배열에 output 데이터 저장하기
    }
    jarisu = jarisu * 10
}

코드 구현하기

/**
 * 10989) 수_정렬하기_3
 */
public class D022_10989 {
    public static int[] A;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        // N(정렬할 수 개수)
        int N = Integer.parseInt(br.readLine());
        // A(정렬할 배열 선언하기)
        A = new int[N];
        // A 배열 저장하기
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(br.readLine());
        }
        br.close();
        // 기수 정렬 함수 수행하기
        Radix_Sort(A, 5);
        // 정렬된 A 배열 출력하기
        for (int i = 0; i < N; i++) {
            bw.write(A[i] + "\n");
        }
        bw.flush();
        bw.close();
    }

    // 기수 정렬 함수
    public static void Radix_Sort(int[] A, int max_size) {
        // output(임시 정렬을 위한 배열)
        int[] output = new int[A.length];
        // jarisu(현재 자릿수를 표현하는 수 -> 1, 10, 100, ...)
        int jarisu = 1;
        // 최대 자릿수만큼 반복하기
        int count = 0;
        while (count != max_size) {
            // bucket(현재 자릿수들의 분포를 합 배열의 형태로 알려 주는 배열 0 ~ 9)
            int[] bucket = new int[10];
            // 일의 자리부터 시작하기
            for (int i = 0; i < A.length; i++) {
                bucket[(A[i] / jarisu) % 10]++;
            }
            // 합 배열을 이용해 index 계산하기
            for (int i = 1; i < 10; i++) {
                bucket[i] += bucket[i - 1];
            }
            // 현재 자릿수를 기준으로 정렬하기
            for (int i = A.length - 1; i >= 0; i--) {
                output[bucket[A[i] / jarisu % 10] - 1] = A[i];
                bucket[(A[i] / jarisu) % 10]--;
            }
            // 다음 자릿수 이동을 위해 현재 자릿수 기준 정렬 데이터 저장하기
            for (int i = 0; i < A.length; i++) {
                A[i] = output[i];
            }
            // 자릿수 증가시키기
            jarisu = jarisu * 10;
            count++;
        }
    }
}