백준 : 1517

https://www.acmicpc.net/problem/1517

1517번: 버블 소트

 

package day0225;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;
 
public class B1517 {
    static long Answer;
    static int arrcopy[];
    static int arr[];
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int N = Integer.parseInt(br.readLine());
        arr = new int[N];
        arrcopy = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Answer = 0;
        Merge(0, N - 1);
        System.out.println(Answer);
    }
 
    public static void Merge(int left, int right) {
 
        if (left != right) {
            int mid = (left + right) / 2;
            Merge(left, mid);
            Merge(mid + 1, right);
            MergeSort(left, right);
        }
    }
 
    private static void MergeSort(int left, int right) {
        int mid = (left + right) / 2;
        int i = left;
        int j = mid + 1;
        int k = left;
 
        while (i <= mid && j <= right) {
            if (arr[i] > arr[j]) {
                arrcopy[k++] = arr[j++];
                Answer+= mid -i+1;
            }
            else {
                arrcopy[k++] = arr[i++];
 
            }
        }
 
        if (i > mid) {
            while (j <= right) {
                arrcopy[k++] = arr[j++];
            }
        } else {
            while (i <= mid) {
                arrcopy[k++] = arr[i++];
            }
        }
 
        for (k = left; k <= right; k++) {
            arr[k] = arrcopy[k];
        }
    }
}