[BOJ] 백준 10090 Counting Inversions

출처: https://www.acmicpc.net/problem/10090

Approach

합병 정렬(Merge Sort)  

합병 정렬(Merge Sort)

▷ (4,2) (4,1) (4,3) (2,1) (7,1) (7,5) (7,6) (7,3) (5,3) (6,3) 총 10개　

 

완전탐색의 경우에는 O(N2)으로 TLE 발생.

병합정렬에서 Merge되는 과정을 이용합니다. O(N logN)

Inversion 개수 = 1 + 1 + 4 + 3 + 8 = 17

Merge 되는 과정에서 우측에 있는 숫자들이 왼쪽에 있는 숫자보다 작아서

재배치되는 경우가 Inversion한 상황이므로 이 경우를 구합니다. 

---

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
  
public class Main {
    static int[] arr, temp;
    static long answer = 0;
     
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
         
        int N = Integer.parseInt(br.readLine());
        arr = new int[N+1]; 
        temp = new int[N+1];
         
        st = new StringTokenizer(br.readLine());;
        for(int i=1; i<=N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
         
        mergeSort(1, N);
         
        System.out.println(answer);
    }
     
    public static void mergeSort(int left,int right) { 
        if(left >= right) return;  
         
        int mid = (left + right) / 2;
        mergeSort(left, mid);
        mergeSort(mid + 1, right);
        merge(left, mid, right);    
    }
     
    public static void merge(int left, int mid, int right) {
        int x = left; 
        int y = mid + 1;    
        int k = left;    
         
        while(x <= mid || y <= right) {    
            if (y > right || (x <= mid && arr[x] < arr[y])) {
                temp[k] = arr[x++];
            }
            else {
                answer += (mid - x + 1);
                temp[k] = arr[y++];
            }
            k++;
        }
         
        for(int i=left; i<=right; i++) {
            arr[i] = temp[i];
        }
    }
}