코딩 테스트 [정렬] - 수 정렬하기 3

유의선·2023년 8월 4일

N개의 수가 주어졌을 때 이를 오름차순 정렬하는 프로그램을 작성하시오.

(시간 제한 3초)

입력

1번째 줄에 수의 개수 N(1 ⪯ N ⪯ 10,000,000), 2번째 줄부터 N개의 줄에 숫자가 주어진다. 이 수는 10,000 보다 작거나 같은 자연수다.

출력

1번째 줄부터 N개의 줄에 오름차순 정렬한 결과를 1줄에 1개씩 출력한다.

`1단계` - 문제 분석하기

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

`2단계` - 손으로 풀어 보기

자릿수가 서로 다른 경우 자릿수가 적은 0이 채워져 있다고 생각하여 큐에 삽입하면 된다.

최초에는 일의 자릿수를 기준으로 큐에 삽입하고, 큐에서 순서대로 pop한다.

이어서 십의 자릿수를 기준으로 큐에 삽입하고 정렬한다.
이 때 8과 같은 수는 008이라고 생각하여 0위치의 큐에 삽입한다.

백의 자릿수 기준도 같은 과정을 진행한다.

최종 정렬 결과는 8, 15, 24, 100, 145, 198, 215, 294, 344, 372, 831 이다.

`3단계` - sudo코드 작성하기

N(정렬할 수 개수)
A(정렬할 배열 선언하기)

for(N의 개수만큼 반복하기)
{
	A 배열 저장
}

기수 정렬 함수 수행
정렬된 A 배열 출력

// 기수 정렬 함수 구현하기
기수 정렬(A, N)
{
	A(배열), N(최대 자릿수)
    
    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
    }
}

`4단계` - 코드 구현하기

import java.io.*;

public class Q22 {
    public static int[] A;
    public static long result;

    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());

        A = new int[N];
        for(int i = 0; i < N; i++){
            A[i] = Integer.parseInt(br.readLine());
        }

        br.close();

        Radix_Sort(A, 5);

        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){
        int[] output = new int[A.length];
        int jarisu = 1;
        int count = 0;

        while(count != max_size){

            int[] bucket = new int[10];

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

            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++;

        }
    }
}