[Baekjoon] 1517번: 버블 소트 (Platinum) - C++ 풀이

정렬 세그먼트 트리 분할 정복

💾 메모리: 9832 KB, 시간: 108 ms📅 2026년 2월 4일 01:33:01

문제 링크

문제 설명

N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오.

버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1 이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므로 2 1 3 이 된다. 다음에는 2, 1이 바뀌어야 하므로 1 2 3 이 된다. 그러면 더 이상 바꿔야 할 경우가 없으므로 정렬이 완료된다.

입력

첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다.

출력

첫째 줄에 Swap 횟수를 출력한다

코드 (C++)

#include <iostream>
#include <string>

using namespace std;

long long arr[500005];
long long set[500005];
long long cnt = 0;

void merge(int left, int mid, int right)
{
    int i, j, k, l;
    i = left;
    j = mid + 1;
    k = left;

    while (i <= mid && j <= right)
    {
        if (arr[i] <= arr[j])
        {
            set[k++] = arr[i++];
        }
        else
        {
            cnt += (long long)(mid - i + 1);
            set[k++] = arr[j++];
        }
    }

    if (i > mid)
    {
        for (l = j; l <= right; l++)
        {
            set[k++] = arr[l];
        }
    }
    else
    {
        for (l = i; l <= mid; l++)
        {
            set[k++] = arr[l];
        }
    }

    for (l = left; l <= right; l++)
    {
        arr[l] = set[l];
    }
}
void Msort(int left, int right)
{
    int mid = (left + right) / 2;

    if (left < right)
    {
        Msort(left, mid);
        Msort(mid + 1, right);
        merge(left, mid, right);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N;
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> arr[i];

    Msort(0, N - 1);

    // cout<<"( ";
    // for (int i = 0; i < N; i++)
    //     cout<<arr[i]<<" ";
    // cout<<")\n";
    cout << cnt;
}