[백준, BOJ 1517] 버블 소트 (java)

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

메모리: 19,4524 KB , 시간: 536 ms

사용 알고리즘: 분할 정복, 정렬

728x90

---

버블 소트로 문제를 해결하면 $O(N^2)$

머지 소트로 문제를 해결하면 $O(NlogN)$

따라서, 문제 제목은 버블 소트이지만 머지 소트로 답을 구해야 한다.

 

분할 정복 과정에서

정렬된 두 배열 left와 right가 있고, 두 배열을 정렬하며 합쳐야 한다.

left[idxL]과 right[idxR]을 비교하며 ret 배열에 담다가

left[idxL] > right[idxR]인 지점에서

버블 소트였다면 right[idxR]을 left[idxL] ~ left[left.length - 1]들과 swap해주는 과정이 일어났을 것이다.

따라서 answer에 left.length - idxL를 더해주면 swap이 발생하는 횟수를 구할 수 있다.

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

public class Main {

    static long answer;

    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int[] A = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        answer = 0;
        mergeSort(A);
        System.out.println(answer);
    }

    private static int[] mergeSort(int[] arr) {

        if(arr.length == 1) return arr;

        int mid =  arr.length / 2;
        int[] left = mergeSort(Arrays.copyOfRange(arr, 0, mid));
        int[] right = mergeSort(Arrays.copyOfRange(arr, mid, arr.length));

        int[] ret = new int[arr.length];
        int idx = 0, idxL = 0, idxR = 0;
        while(idxL < left.length && idxR < right.length) {
            if(left[idxL] <= right[idxR]) ret[idx++] = left[idxL++];
            else {
                answer += left.length - idxL;
                ret[idx++] = right[idxR++];
            }
        }
        while(idxL < left.length) ret[idx++] = left[idxL++];
        while(idxR < right.length) ret[idx++] = right[idxR++];

        return ret;
    }
}