[백준] 1517번 버블 소트 문제 Merge Sort로 풀어보기 (버블 소트로는 풀 수 없는 이유?)
1. 문제
문제는 위의 링크에 들어가면 확인할 수 있다.
2. 풀이
이 문제는 버블 소트를 할 때 수를 바꾸는 과정이 몇 번 있는지를 묻는 문제이다. 하지만 이것을 실제 Bubble Sort대로 풀면 시간초과가 나게 될 것이다. 왜냐하면 버블소트는 시간복잡도 O(N^2) 이기 때문에 문제에서 주어진 조건을 초과하게 된다.
따라서 이 문제는 시간복잡도 O(NlogN)인 merge sort를 활용하여서 풀 수 있다.
버블 소트는 index i, j에 대해서 i<j인데 a[i] > a[j] 일때 두 수를 바꾸어주는 알고리즘을 의미한다.
그래서 이를 merge sort라고 생각하면, 두 그룹을 합쳐줄 때 버블 소트에서 두 수를 바꾸어주는 count를 세어 줄 수 있다.
다시 말해서,
.png)
위와 같은 두 그룹을 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라는 배열에 담을 때 첫 번째 그룹의 원소개수를 정답에 추가해주어야 한다는 점이다.
.png)
.png)
.png)
.png)
.png)
.png)
.png)