[SWEA 3998] Inversion Counting - C++

SW Expert Academy

문제

길이 N의 수열 A가 주어진다. A의 원소들을 각각 A[1], A[2], ... , A[N]이라고 할 때 i < j 인데 A[i] > A[j] 라면 (A[i], A[j])를 Inversion이라고 한다. (단, 1 ≤ i < j ≤ N)
주어진 순열에서 Inversion의 수를 구하는 프로그램을 작성하라.

입력

첫 줄에 테스트케이스의 개수 T가 주어진다. (T ≤ 20)
입력은 여러개의 테스트 케이스로 이루어져 있으며 테스트 케이스의 개수가 첫 줄에 주어진다. 각 테스트 케이스는 총 2줄로 구성되어있으며,
첫 줄에는 순열의 길이를 나타내는 수 N(2 ≤ N ≤ 100,000)이 주어진다.
다음 줄에는 N개의 수가 공백으로 구분되어 주어지며 이는 순열을 의미한다. 즉, 1부터 N까지의 수가 한번씩 주어진다.

풀이

#include <iostream>
 
using namespace std;
 
int input[100001];
int temp[100001];
long long answer;
 
void mergesort(int start, int end)
{
    int mid;
    if (start < end)
    {
        mid = (start + end) / 2;
        mergesort(start, mid);
        mergesort(mid + 1, end);
        int left = start, right = mid + 1, idx = start;
        while (left <= mid || right <= end)
        {
            if (right > end || (left <= mid && input[left] < input[right]))
            {
                temp[idx] = input[left];
                left += 1;
                idx += 1;
            }
            else
            {
                answer += (mid - left + 1);
                temp[idx] = input[right];
                right += 1;
                idx += 1;
            }
        }
        for (int i = start; i <= end; i++)
        {
            input[i] = temp[i];
        }
    }
}
 
int main(int argc, char** argv)
{
    int test_case;
    int T;
    //freopen("input.txt", "r", stdin);
    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case)
    {
        int N;
        answer = 0;
        cin >> N;
        for (int i = 0; i < N; i++)
        {
            cin >> input[i];
        }
        mergesort(0, N - 1);
        cout << "#" << test_case << " " << answer << endl;
 
    }
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

해결방법

조건에서 설명한 Inversion 상태를 찾기 위해서 병합 정렬을 활용하면 됩니다.

병합 정렬 수행 (mergesort 함수)

 

• 재귀적으로 배열을 반으로 나눈 후, 각각을 정렬하여 병합합니다.
• 병합하는 과정에서 역순 쌍을 카운트합니다.
• 역순 쌍이 발생하는 경우는 왼쪽 부분 배열의 값이 오른쪽 부분 배열의 값보다 큰 경우입니다.
• 이때, 왼쪽 배열의 현재 위치에서 끝까지 남은 모든 원소가 현재 오른쪽 값보다 크므로 (mid - left + 1)개 만큼 역순 쌍이 존재합니다.