In this post, solution of BoJ 1629 is introuduced.

1629

• level : Silver 1
• Problem : Here

Solution

• Input $a, b, c$ 에 대해 $a^b \ mod \ c$ 를 구하는 문제이다,

• $a^b \ mod \ c = (a\mod c)^(b \ mod \ c)$ 을 이용하여

시간복잡도는

1. Best Case :
2. Avg Case :
3. Worst Case :

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

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

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

  시간복잡도는

  1. ㅇ

  최종 코드는 아래와 같다.

  // 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];
          } 
        
      }
  }