백준 1517 자바 - 버블 소트

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

1517번: 버블 소트

문제

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 이 된다. 그러면 더 이상 바꿔야 할 경우가 없으므로 정렬이 완료된다.

코드

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] a = new int[n];
        String[] line = br.readLine().split(" ");
        for (int i = 0; i < n; i++) a[i] = Integer.parseInt(line[i]);

        bw.write(String.valueOf(solve(a, 0, n - 1)));
        bw.flush();
    }

    private static long solve(int[] a, int start, int end) {
        if (start == end) return 0L;

        int middle = (start + end) / 2;
        int[] b = new int[end - start + 1];

        long answer = solve(a, start, middle) + solve(a, middle + 1, end);

        int i = start, j = middle + 1, k = 0;

        while (i <= middle || j <= end) {
            if (i <= middle && (j > end || a[i] <= a[j])) {
                b[k++] = a[i++];
            } else {
                answer += (middle - i + 1);
                b[k++] = a[j++];
            }
        }
        for (int index = start; index <= end; index++) a[index] = b[index - start];
        return answer;
    }
}

풀이

버블 소트로 풀면 통과가안되는 버블 소트 문제다(..?). 대신 병합정렬을 써서 풀었다. 병합 과정에서 왼쪽 값이 오른쪽 값 보다 크면 왼쪽 배열의 원소의 개수를 answer 변수에 더해주었다. 이 값을 마지막에 출력한다.