백준 1517 - 버블 소트

문제

 

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

1517번: 버블 소트

 

 

풀이

 

수열의 왼쪽에 있는 수가 오른쪽에 있는 수보다 몇 개가 더 큰지 알아내면 된다. 그 수 만큼 버블 정렬에서 swap이 일어나기 때문이다. 

수열 1 3 5 2 4 의 경우 3은 2보다 크고, 5는 2와 4보다 크므로 버블 정렬에서 swap이 총 세번 일어난다. 

 

병합 정렬을 이용해 왼쪽에 있는 수가 오른쪽에 있는 수보다 몇 개가 더 큰지 구할 수 있다. R 배열의 값을 새로운 정렬할 배열에 넣을 때 L 배열에 남아 있는 수를 더하면 된다. 

수열 1 3 5 2 4 의 경우 L = [1, 3, 5], R = [2, 4] 가 되고

R 배열에서 2를 추가할 때 L 배열에는 [3, 5] 가 남아서 2가 추가 되고

R 배열에서 4를 추가할 때 L 배열에는 [5] 만 남아서 1이 추가 되서 답은 3이 된다.

 

 

코드

 

#include <iostream>
 
using namespace std;
 
int N;
int A[500000];
int B[500000];
long long result;
 
void merge(int l, int mid, int r)
{
    int i = l;
    int j = mid+1;
    int idx = 0;
    while (i <= mid || j <= r)
    {
        if (i <= mid && (j > r || A[i] <= A[j]))
            B[idx++] = A[i++];
        else
        {
            B[idx++] = A[j++];
            result += (long long)mid - i + 1;
        }   
    }
 
    for (int i=l; i<=r; i++) A[i] = B[i-l];
}
 
void mergesort(int l, int r)
{
    if (l < r)
    {
        int mid = (l+r) / 2;
        mergesort(l, mid);
        mergesort(mid+1, r);
        merge(l, mid, r);
    }
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    cin >> N;
    for (int i=0; i<N; i++) cin >> A[i];
 
    mergesort(0, N-1);
 
    cout << result;
 
    return 0;
}