[ BOJ ][JAVA][1517] 버블 소트

www.acmicpc.net/problem/1517

1517번: 버블 소트

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	12334	3075	2047	28.486%

문제

N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오.

버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1 이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므로 2 1 3 이 된다. 다음에는 2, 1이 바뀌어야 하므로 1 2 3 이 된다. 그러면 더 이상 바꿔야 할 경우가 없으므로 정렬이 완료된다.

입력

첫째 줄에 N(1≤N≤500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0≤|A[i]|≤1,000,000,000의 범위에 들어있다.

출력

첫째 줄에 Swap 횟수를 출력한다

예제 입력 1

3
3 2 1

예제 출력 1

3

코드

import java.io.*;
import java.util.*;
public class p1517 {
    static int n;
    static long cnt, arr[], sorted[];
    static BufferedReader br;
    static StringTokenizer st;
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        cnt = 0;
        arr = new long[n];
        sorted = new long[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; ++i) {
            arr[i] = Long.parseLong(st.nextToken());
        }
        mergeSort(0, n - 1);
        System.out.println(cnt);
    }   

    static void mergeSort(int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(left, mid);
            mergeSort(mid+ 1, right);
            merge(left, mid, right);
        }
    }

    static void merge(int left, int mid, int right) {
        int i = left;
        int j = mid + 1;
        int idx = left;

        while (i <= mid && j <= right) {
            if(arr[i] <= arr[j]) {
                sorted[idx++] = arr[i++];
            } else {
                sorted[idx++] = arr[j++];
                cnt += (mid + 1 - i);
            }
        }

        while(i <= mid) {
            sorted[idx++] = arr[i++];
        }
        while(j <= right) {
            sorted[idx++] = arr[j++];
        }

        for (int k = left; k <= right; k++) {
            arr[k] = sorted[k];
        }

    }
}