1. 문제

2. 아이디어

• 단순 정렬 문제
• 시간 제한, 메모리 제한이 있음으로 기수 정렬 Radix Sort 를 이용하기로 한다.

3. 코드

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

class Main {  
  public static void main(String args[]) throws Exception{ 
    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());
    }
    RadixSort.radixSort(arr);

    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    for(int res:arr){
      bw.write(Integer.toString(res)+"\n");
    }
    bw.flush();
    bw.close();
  } 
}

class RadixSort{
  public static void radixSort(int[] arr){
    int n = arr.length;
    int max = 0;
    for(int i =0;i<n;i++) max = Math.max(max, arr[i]);

    for(int exp = 1; max / exp > 0; exp *= 10){
      countSort(arr, n, exp);
    }
  }

  public static void countSort(int[] arr, int n, int exp){
    int[] buffer = new int[n];
    int[] counting = new int[10];

    for(int i =0;i<n;i++) counting[(arr[i] / exp) % 10] ++;
    for(int i =1;i<10;i++) counting[i] += counting[i-1];

    for(int i = n-1;i>=0;i--){
      int res = (arr[i] / exp) % 10;
      int index = counting[res];
      buffer[index-1] = arr[i];
      counting[res] --;
    }

    for(int i =0;i<n;i++){
      arr[i] = buffer[i];
    }
  }
}

4. 배운 점, 느낀 점

• Radix Sort 기수 정렬
  • 1의 자리부터 점층적으로 각 숫자끼리 비교하여서 정렬하는 것이다.
  • 시간복잡도는 O(dn) 이다