1. 문제

📌 문제 보러 가기!

2. 접근법

• 제목은 버블 소트이지만 버블소트는 O(N^2)의 시간복잡도를 가지고 있어, 버블소트를 사용하면 시간초과가 난다.
• 머지소트를 활용해 스왑 횟수를 알아낸다.
• 머지소트 진행 시, 뒤쪽 배열의 값이 선택될 때는 앞쪽 배열의 남은 수만큼 스왑이 일어났다고 판단한다
• 즉, 뒤쪽 배열의 값을 고를 때 앞쪽 배열의 남은 수만큼 결과값을 증가시킨다

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BaekJoon1517 {
    public static int[] arr, tmp;
    public static long ans;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        arr = new int[N + 1];
        tmp = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        ans = 0;
        mergeSort(1, N);

        System.out.println(ans);
    }

    private static void mergeSort(int l, int r) {
        if (l < r) {
            int m = l + (r - l) / 2;

            mergeSort(l, m);
            mergeSort(m + 1, r);

            merge(l, r, m);
        }
    }

    private static void merge(int l, int r, int m) {
        for (int i = l; i <= r; i++) {
            tmp[i] = arr[i];
        }
        int k = l;
        int index1 = l;
        int index2 = m + 1;
        while (index1 <= m && index2 <= r) {
            if (tmp[index1] > tmp[index2]) {
                arr[k] = tmp[index2];
                ans = ans + index2 - k;
                k++;
                index2++;
            } else {
                arr[k] = tmp[index1];
                k++;
                index1++;
            }
        }
        while (index1 <= m) {
            arr[k] = tmp[index1];
            k++;
            index1++;
        }
        while(index2 <= r) {
            arr[k] = tmp[index2];
            k++;
            index2++;
        }
    }
}