[백준] 1517번 버블 소트 문제 Merge Sort로 풀어보기 (버블 소트로는 풀 수 없는 이유?) : Programming Story

1. 문제

www.acmicpc.net/problem/1517

문제는 위의 링크에 들어가면 확인할 수 있다.

2. 풀이

이 문제는 버블 소트를 할 때 수를 바꾸는 과정이 몇 번 있는지를 묻는 문제이다. 하지만 이것을 실제 Bubble Sort대로 풀면 시간초과가 나게 될 것이다. 왜냐하면 버블소트는 시간복잡도 O(N^2) 이기 때문에 문제에서 주어진 조건을 초과하게 된다.

따라서 이 문제는 시간복잡도 O(NlogN)인 merge sort를 활용하여서 풀 수 있다.

버블 소트는 index i, j에 대해서 i<j인데 a[i] > a[j] 일때 두 수를 바꾸어주는 알고리즘을 의미한다.

그래서 이를 merge sort라고 생각하면, 두 그룹을 합쳐줄 때 버블 소트에서 두 수를 바꾸어주는 count를 세어 줄 수 있다.

다시 말해서,

위와 같은 두 그룹을 merge sort를 통해서 합쳐준다고 생각하면 첫 그룹의 7과 두번째 그룹의 1을 비교해서 1이 먼저 앞으로 들어가게 된다.

Bubble Sort라고 생각해보면 7, 9, 1, 3이 다 합쳐져있었을 것이고 1을 기준으로 7과 1이 한번 교환되었을 것이고, 9과 1이 한번 더 교환되었을 것이다. 그러면 1 기준으로 두 번의 숫자 교환이 이루어졌던 것이다.

우리는 merge sort를 통해서 구현하고 있었으니 이를 merge sort로 생각해보면 두 번째 그룹인 1이 가장 처음에 들어갈 때 앞에 남아있는 그룹의 원소 개수만큼 숫자의 교환이 이루어지는 것이다. 여기서는 1이 가장 먼저 정렬될 때 첫 번째 그룹에 7,9 이렇게 두 개의 숫자가 남아있으니 답에는 2가 더해지게 되는 것이다. 마찬가지로 3의 경우에도 3이 정렬될 때 첫 번째 그룹에 두 개의 숫자가 남아있으니 답에는 추가로 2만큼 더해주어야 한다.

3. 코드

이를 코드로 구현한 것은 아래와 같다.

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

public class Main{
    static int a[];
    public static long go(int start, int end){
        if (start==end){
            return 0;
        }
        int mid=(start+end)/2;
        long ans=go(start, mid)+go(mid+1, end);
        int [] tmp=new int[end-start+1];
        { //두 그룹을 합칠 때 merge
            int i=start;
            int j=mid+1;
            int k=0;
            while(i<=mid || j<=end){
                if (i<=mid && (j>end||a[i]<=a[j])){
                    tmp[k++]=a[i++];
                }else{
                    ans+=(long)(mid-i+1);  //두번째 그룹의 숫자가 들어갈 때 
                    tmp[k++]=a[j++];
                }
            }
            
        }
        for (int i=start; i<=end; i++) {
            a[i] = tmp[i-start];
        }
        return ans;
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.valueOf(br.readLine());
        a=new int[n];
        String s[]=br.readLine().split(" ");
        for(int i=0; i<n; i++){
            a[i]=Integer.valueOf(s[i]);
        }
        System.out.println(go(0, n-1));
    }
}

merge sort의 구현을 그대로 따라주었고 다른 점은 두 번째 그룹의 숫자를 tmp라는 배열에 담을 때 첫 번째 그룹의 원소개수를 정답에 추가해주어야 한다는 점이다.