1. 문제

2. 아이디어

• 버블 소트는 한칸씩 옮겨가면서 작은 수와 큰 수를 swapping 하는 방법이다.
• 그리고 이러한 방식은 MergeSort 에서도 유사한 방식을 사용한다.
• MergeSort 에서 원래의 index - 바뀐 index (단, 원래의 index 가 더 클 때만)의 합이 버블 소트에서 swapping 한 횟수일 것이다.

3. 코드

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

class Main {
  public static long cnt;
  public static void main(String args[]) throws Exception{ 
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    
    int N = Integer.parseInt(br.readLine());
    long[] arr = new long[N];

    st = new StringTokenizer(br.readLine());
    for(int i =0 ;i < N;i++){
      arr[i] = Long.parseLong(st.nextToken());
    }
    mergeSort(arr);
    System.out.println(cnt);
  }

  public static void mergeSort(long[] arr){
    mergeSort(arr, 0, arr.length);
  }

  public static void mergeSort(long[] arr, int low, int high){
    if(high - low < 2) return;

    int mid = (low + high) /2;
    mergeSort(arr, low, mid);
    mergeSort(arr, mid, high);
    merge(arr, low, mid, high);
  }

  public static void merge(long[] arr, int low, int mid, int high){
    long[] tmp = new long[high - low];
    int l = low, h = mid, t = 0;

    while(l < mid && h < high){
      if(arr[l] <= arr[h]){
        tmp[t++] = arr[l++];
      }
      else{
        cnt += (h - (t+low));
        tmp[t++] = arr[h++];
      }
    }

    while(l < mid){
        tmp[t++] = arr[l++];
    }

    while(h < high){
        tmp[t++] = arr[h++];
    }

    for(int i = low;i<high;i++){
      arr[i] = tmp[i - low];
    }
  }
}

4. 배운 점, 느낀 점

• 데이터의 길이가 너무 길면 Integer 보다는 long 을 쓰는 것이 맞다.