In this post, solution of BoJ 2751 is introuduced.

2751

• level : Silver 5
• Problem : Here

Solution

• 문제에서 Input 개수의 크므로 (N < 1000000), $O(nlogn)$ 알고리즘을 연습한다.

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

• 정렬하고자 하는 배열의 영역을 output과 input 영역으로 나누어 (초기에는 output 영역이 없다) 원소를 하나씩 차례로 output 영역으로 보낸댜. output 영역은 항상 sorting 된 상태로 유지된다. i 번째 단계 후, 1~i 번째 원소가 output 영역에서 최종 정렬된 위치로 배치된다 (매 iteration 마다 끝에서 부터 양옆의 원소와 비교를 한다).

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

  시간복잡도는

  1. Best Case : $O(n^2/2)$ 완전히 정렬된 경우 (swap 없음. 비교만 있음).
  2. Avg Case : $O(3n^2/4)$
  3. Worst Case : $O(n^2)$ 완전히 역정렬된 경우.

• Bubble Sort는 기본적으로 느린 알고리즘이다. 결과적으로 시간초과가 나 다른 알고리즘을 사용했다.

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

• Divide and Conquer 전략을 사용하여 하나의 배열을 반으로 쪼개 각각의 배열을 정렬한 다음 다시 합치는 방식을 재귀적으로 구현한다.

  시간복잡도는

  1. 모든 case 에서 $O(n)$

  최종 코드는 아래와 같다. 마지막 남는 원소들을 배열에 채워넣는 부분을 for 대신 while 문을 쓴다면 조금 더 간단히 작성할 수 있을 것이다.

  // 250905
  // 2751
  // sorting - O(n^2) - Bubble Sort
  // 시간초과
    
  import java.io.*;
    
  public class MergeSort{
      public static void main(String[] args) throws Exception{
          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());
          }
    
          MergeSort ms = new MergeSort();
          ms.mergeSort(arr, 0, n - 1);
    
          StringBuilder sb = new StringBuilder();
          for (int i = 0; i < n; i++){
              sb.append(arr[i]).append('\n');
          }
    
          bw.write(sb.toString());
          bw.flush();
          bw.close();
          br.close();
    
      }
    
      public void mergeSort(int[] arr, int l, int r){
          if (l == r) return;
          else{
              int m = (l + r) / 2;
              mergeSort(arr, l, m);
              mergeSort(arr, m + 1, r);
              merge(arr, l, r);
          }
      }
    
      public void merge(int[] arr, int l, int r){
          if (l == r) return;
    
          int m = (l + r) / 2; // l=1, r=2, -> m=1
        
          int[] temp = new int[r - l + 1];
          int idx = 0;
    
          int l_idx = l;
          int r_idx = m + 1;
          while ((l_idx <= m) && (r_idx <= r)){
              if (arr[l_idx] < arr[r_idx]){
                  temp[idx] = arr[l_idx];
                  l_idx++;
                  idx++;
              }else{
                  temp[idx] = arr[r_idx];
                  r_idx++;
                  idx++;
              }
          }
          // l = 1, r = 7, m = 4
          // l_idx = 4, r_idx = 6
          // 1~4는 왼쪽 배열, 5~7는 오른쪽 배열
    
          if (l_idx == m + 1){
              int r_left = r - r_idx + 1;
              for (int i = 0; i < r_left; i++){
                  temp[idx] = arr[r_idx];
                  r_idx++;
                  idx++;
              }
          }else if (r_idx == r + 1){
              int l_left = m - l_idx + 1;
              for (int i = 0; i < l_left; i++){
                  temp[idx] = arr[l_idx];
                  l_idx++;
                  idx++;
              }
          }
          for (int i = 0; i < r - l + 1; i++){
              arr[l+i] = temp[i];
          } 
        
      }
  }