In this post, solution of BoJ 10989 is introuduced.

10989

• level : Bronze 1
• Problem : Here

Solution

• Bin Sort 란, 0 ~ n-1 까지 정수들의 중복 순열을 효과적으로 sorting 하는 문제를 해결하기 위해 고안된 sorting 알고리즘이다.

• 중복한 순열의 숫자 범위가 0 ~ n-1 (n-1은 반드시 존재한다고 가정, 이를 MaxKey 라 하자.) 이고, 정렬해야 할 기존 배열 A의 길이가 m 이라고 할 때

  for (i=0; i<n; i++){
    S[i] = 0;
  } // O(MaxKey)
  for (i=0; i<m; i++){
    S[A[i]]++;
  } // O(m)
  

  다음과 같이 k번째 원소로 숫자 k가 몇 번 쓰였는지를 저장하는 길이 n의 배열 S를 얻을 수 있다. 이 때의 시간복잡도는 $O(MaxKey + n)$ 이다.

• Bin Sort는 MaxKey의 값이 작으면 running time이 빠르고 space requirement도 적어지지만 MaxKey의 값이 크면 running time이 느려지고 space requirement도 커진다는 단점이 있다.

  실제로 이 문제를 Bin Sort 로 해결하기 위해 다음과 같이 코드를 작성하면 시간 초과가 뜬다.

  // 250621 
  // 10989
  // Bin Sort
  // 시간 초과
  import java.util.Scanner;
    
  class BinSort{
      public static void main(String[] args){
          Scanner sc = new Scanner(System.in);
    
          int n = sc.nextInt();
          sc.nextLine();
    
          int [] count = new int[10001];
          for (int i = 0; i < 10001; i++){
              count[i] = 0;
          }
          for (int i = 0; i < n; i++){
              count[sc.nextInt()]++;
              sc.nextLine();
          }
    
          System.out.println();
          sc.close();
          for (int i = 0; i < 10001; i++){
              if (count[i] != 0){
                  for (int j = 0; j < count[i]; j++){
                      System.out.println(i);
                  }
              }
          }
      }
  }
  

  사실 이 문제에서 시간 초과가 뜬 결정적인 이유는 알고리즘의 문제라기 보다는 Scanner 와 System.out 기반의 I/O가 너무 느리기 때문이다. 이를 BufferedReader 와 StringBuilder 를 이용해서 해결했고 최종 코드는 아래와 같다. 자바에서 효율적으로 I/O를 처리하는 방법에 대해서는 여기 참고 바람.

  import java.io.*;
    
  public class Binsort {
      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());
          int[] count = new int[10001];
    
          // 입력 받기
          for (int i = 0; i < n; i++) {
              count[Integer.parseInt(br.readLine())]++;
          }
    
          // 출력 모으기
          StringBuilder sb = new StringBuilder();
          for (int i = 1; i <= 10000; i++) {
              while (count[i]-- > 0) {
                  sb.append(i).append('\n');
              }
          }
    
          // 최종 출력
          bw.write(sb.toString());
          bw.flush();
          bw.close();
          br.close();
      }
  }