10989번 문제 링크

Java11의 경우, 제한시간 3초의 문제이다. 정렬 갯수가 최대 1000만개 이기 때문에, O(nlogn) 보다 빠른 알고리즘을 적용해줘야 합니다.

그 중 "카운팅 정렬" 을 이용하여 해당 문제를 풀어보겠습니다.

알고리즘 로직은 다음과 같습니다.
1. N개의 요소들을 담을 arr 배열을 선언합니다.
2. arr 배열에 담긴 요소를 counting 하기 위한 counting 배열을 선언합니다.(배열 길이 = arr 요소의 최대값)
3. arr 배열을 순회하며 요소를 index로 갖는 counting 배열의 요소에 1을 증가시킵니다.
4. counting 배열의 누적합을 구합니다.
5. arr를 순회하며 counting 배열의 횟수만큼 출력을 해줍니다.
6. 결과적으로 arr를 정렬한 배열이 출력됩니다.

핵심 로직

• 자릿수 마다 0~9의 숫자만 나오는 것을 확인하고 해당 값을 카운팅하여 정렬하는 방식으로 구현하였습니다.
• 예를 들면, 12, 3, 5, 1, 11, 4, 25 라는 수열에서 1의 자릿수를 비교하여 정렬한 경우 → 1, 11, 12, 3, 4, 5, 25 로 정렬됩니다.
• 이를 다시 10의 자리로 정렬할 경우, 01,03,04,05,11,12,25 라는 수로 정렬됩니다.
• 위와 같이 counting 배열 요소를 10개로 고정한 상태에서 자릿수 연산을 통해 10의 자리, 100의 자리,... 기준으로 정렬이 가능하도록 구현하였습니다.

😀 성공

import java.io.*;
import java.util.*;

public class Main{
    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());
        }
        
        // 카운팅 정렬 - 10,000자리이기 때문에 5
        radixSort(arr,5);
        
        StringBuilder sb = new StringBuilder();
        for(int a : arr){
            sb.append(a).append("\n");
        }
        
        System.out.println(sb);
        br.close();
    }
    
    static void radixSort(int[] arr, int max_size){
        int[] output = new int[arr.length];
        int jarisu = 1;
        int count = 0;
        while(count != max_size){
            int[] counting = new int[10];
            
            // 0~9 숫자 중 해당하는 곳에 1증가
            for(int i =0; i < arr.length; i++){
                counting[(arr[i]/jarisu)%10]++;
            }
            
            // 구간합 
            for(int i=1; i<10; i++){
                counting[i] += counting[i-1];
            }
            
            for(int i = arr.length-1; i >= 0; i--){
                output[counting[arr[i]/jarisu%10]-1] = arr[i];
                counting[arr[i]/jarisu % 10]--;
            }
            
            for(int i=0; i< arr.length; i++){
                arr[i] = output[i];
            }
            jarisu *= 10;
            count++;
        }
    }
}