1517번

1517번 - 버블 소트

#########다시 풀어보기###########

분할 정복을 조금 알아갈 것 같은 느낌... 아직도 어렵다 사실

버블 소트가 일어날 때, swap 되는 횟수를 구하는 문제.

처음에 어 쉽네? 하고 N값을 봤더니 50만, 그냥 이중 for문을 통해서 O(N^2) 으로 구하면 구할 수 없는 시간이었다.

그래서 생각해낸 방법은 분할 정복을 써야할 것 같은데..까지밖에 생각 못 했었다.

오래 고민하다가 다른 분들의 풀이를 보고, 아 그런 방법이 있구나 하고 풀었다.

그냥 병합 정렬을 하면서 숫자를 세는 간단하지만, 생각해내지 못한 방법이었다.

병합 정렬에서 왼쪽그룹, 오른쪽 그룹은 항상 오름차순으로 정렬이 되어있다. 

따라서 정렬되어져 있는 왼쪽 그룹 사이 사이로 오른쪽 그룹의 숫자가 들어올 때, swap 이 일어남을 알 수 있다.

그리고 이에 따라 왼쪽 그룹의 남은 갯수만 전체 정답에 계속해서 더해주면 된다..

조심해야 할 점은 첫번째로 정답이 int 의 범위를 벗어난다는 점! 그리고 나 같은 경우에는 중간에 답을 더해주는 과정에서

long long 으로 변환하지 않고 정답을 더해주니까 런타임 오류가 발생했다.

long long 값에 int 형 변수를 더해주고 있었다. 이런 것도 조심해야 겠다!.

<정답 코드>

#include<iostream>
 
using namespace std;
 
int N;
int A[500001];
int tmp[500001];
long long int ans;
void BubbleMergeSort(int start, int end)
{
    int mid = (start + end) / 2;
 
    int left = start;
    int right = mid + 1;
    int i = 0;
 
    while (left<=mid && right<=end)
    {
        if (A[left] > A[right])
        {
            ans += (long long)(mid - left + 1);
            tmp[i++] = A[right++];
        }
        else
        {
            tmp[i++] = A[left++];
        }
    }
    while (left <= mid)
    {
        tmp[i++] = A[left++];
    }
    while (right <= end)
    {
        tmp[i++] = A[right++];
    }
 
    for (int i = start; i <= end; i++)
    {
        A[i] = tmp[i - start];
    }
 
    return;
}
void divide(int start, int end)
{
 
    if (start == end)
    {
        return;
    }
 
    int mid = (start + end) / 2;
 
    divide(start, mid);
    divide(mid + 1, end);
    BubbleMergeSort(start, end);
 
    return;
}
int main()
 
{
    cin >> N;
 
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }
 
    divide(0, N - 1);
 
    cout << ans << endl;
 
    return 0;
}