백준_1517 버블 소트 (병합정렬)

 

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

public class BJ_1517 {

    static int[] arr, tempArr;
    static long result;

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

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

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

        arr = new int[n];
        tempArr = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i=0; i<n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        result = 0;
        mergeSort(0, n-1);

        System.out.println(new StringBuilder().append(result));
    }

    static void mergeSort(int s, int e) {
        if(e-s<1) {
            return;
        }

        int m = (s+e)/2;

        mergeSort(s, m);
        mergeSort(m+1, e);

        int i, j, k;

        for(i=s; i<e+1; i++) {
            tempArr[i] = arr[i];
        }

        i=s;
        j=m+1;
        k=s;

        while(i<m+1 && j<e+1) {
            if(tempArr[i] > tempArr[j]) {
                result += m-i+1;
                arr[k++] = tempArr[j++];
            }
            else {
                arr[k++] = tempArr[i++];
            }
        }

        while(i<m+1) {
            arr[k++] = tempArr[i++];
        }

        while(j<e+1) {
            arr[k++] = tempArr[j++];
        }
    }

}

 

merge sort의 정렬 과정에서 bubble sort의 swap 횟수를 알아낼 수 있다는 힌트를 얻고,

이해하고 풀었는데 계속 시간초과,, 분명 O(nlogn) 으로 가능한 문제인데.

 

알고보니 

tempArr에 arr의 (s,e) 범위를 복붙하는 for에서

i=s로 시작했어야 할 거를 i=0으로 잘못 입력해서 그랬던 것이다.

매번 (0,e) 범위를 tempArr에 저장하려니 시간 초과하는건 당연

 

 

1517번: 버블 소트