In this post, solution of BoJ 2750 is introuduced.

2750

• level : Bronze 2
• Problem : Here

Solution

• 문제에서 Input 개수의 범위가 작으므로 (N < 1000), $O(n^2)$ 알고리즘을 연습한다.

• Insertion Sort 란, 정렬 문제를 해결하기 위해 고안된 sorting 알고리즘이다.

• 정렬하고자 하는 배열의 영역을 output과 input 영역으로 나누어 (초기에는 output 영역이 없다) 원소를 하나씩 차례로 output 영역으로 보낸댜. output 영역은 항상 sorting 된 상태로 유지된다. i 번째 단계에서 i 번째 원소를 output 영역으로 배치시킨다 (양 옆의 원소와 비교하는 bubble sort 와 차이).

  for (int i = 0; i < n; i++){
     for (int j = i; j > 0; j--){
          if (arr[j] < arr[j-1]){
              int temp = arr[j-1];
              arr[j-1] = arr[j];
              arr[j] = temp;
          }
          else{
              break;
          }
     }
  }
  

  시간복잡도는

  1. Best Case : $O(n)$ 완전히 정렬된 경우.
  2. Avg Case : $O(n^2/4)$ (Best + Worst) /2
  3. Worst Case : $O(n^2/2)$ 완전히 역정렬된 경우.

• Insertion Sort는 기본적으로 느린 알고리즘이지만 array 가 거의 정렬되어 있을 때는 very efficient하다.

  최종 코드는 아래와 같다.

  // 250905
  // 2750
  // Sorting - O(n^2) - Insertion Sort
    
  import java.io.*;
    
  public class InsertionSort{
      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[] arr = new int[n];
    
          for (int i = 0; i < n; i++){
              arr[i] = Integer.parseInt(br.readLine());
          }
    
          for (int i = 0; i < n; i++){
             for (int j = i; j > 0; j--){
                  if (arr[j] < arr[j-1]){
                      int temp = arr[j-1];
                      arr[j-1] = arr[j];
                      arr[j] = temp;
                  }
                  else{
                      break;
                  }
             }
          }
    
          StringBuilder sb = new StringBuilder();
          for (int i = 0; i < n; i++){
              sb.append(arr[i]+"\n");
          }
    
          bw.write(sb.toString());
          bw.flush();
          bw.close();
          br.close();
          return;
      }
  }