[백준] 1517번 버블 소트

문제 설명

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

문제 풀이

• 문제는 버블 소트의 SWAP 횟수를 필요로 하지만 버블소트를 사용하면 O(N^2) 시간복잡도로 시간초과가 발생한다.
• 문제는 O(NlogN)알고리즘인 머지소트를 진행하여 SWAP 횟수를 계산하여 풀이하였다.
• 머지소트에서 SWAP 횟수를 판별하는 부분은 부분화된 정렬된 두 배열을 합칠 때 아래와 같이 계산이 가능하다.

  부분 배열 A, 부분 배열 B를 머지할때 각 인덱스를 i, j로 두고 머지하되
  A[i] > B[j]인 경우 SWAP이 발생하는데 이때 SWAP 횟수는 MID(=(start + end)/2) - i + 1이 된다.

• 이는 머지소트 과정을 살펴보면 확인이 가능하다.

소스 코드 (JAVA)

import java.io.*;
import java.util.*;

public class Main {
    public static BufferedReader br;
    public static BufferedWriter bw;

    public static int N;
    public static int[] arr, arr2;

    public static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        arr = new int[N];
        arr2 = new int[N];
        for (int i = 0; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken());
    }

    public static long caculate(int start, int end) {
        if (start == end) return 0;
        int mid = (start + end) / 2;
        //divide
        long result = caculate(start, mid) + caculate(mid + 1, end);
        int i = start;
        int j = mid + 1;
        int ind = 0;
        //부분 배열 합쳐줌 
        while (i <= mid || j <= end) {
            if (i <= mid && (j > end || arr[i] <= arr[j])) {
                arr2[ind++] = arr[i++];
            } else {
                result += (mid - i + 1);
                arr2[ind++] = arr[j++];
            }
        }
        //원래 배열에 결과 반영 
        for (ind = start; ind <= end; ind++)
            arr[ind] = arr2[ind - start];
        return result;
    }

    public static void solve() throws IOException {
        bw.write(caculate(0, N-1) + "\n");
        bw.flush();
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }
}