[BOJ] 10090 번 - Counting Inversions

10090번 - Counting Inversions

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	1690	673	458	39.585%

문제

A permutation of integers from 1 to n is a sequence a1, a2, ..., an, such that each integer from 1 to n is appeared in the sequence exactly once.

Two integers in а permutation form an inversion, when the bigger one is before the smaller one.

As an example, in the permutation 4 2 7 1 5 6 3, there are 10 inversions in total. They are the following pairs: 4–2, 4–1, 4–3, 2–1, 7–1, 7–5, 7–6, 7–3, 5–3, 6–3.

Write program invcnt that computes the number of the inversions in a given permutation.

입력

The value for the number n is written on the first line of the standard input. The permutation is written on the second line: n numbers, delimited by spaces. (2 ≤ n ≤ 1000000)

출력

Write the count of inversions on the standard output.

 

 

---

예제 입력 1

7
4 2 7 1 5 6 3

예제 출력 1

10

출처

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

10090번: Counting Inversions

알고리즘 분류

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

접근 방법

처음 이 문제를 해결했을 때, "앗!" 하는 느낌이 들었는데 이제서야 복습 겸 풀이 하고자 한다.

먼저, 해당 문제를 해결할 수 있는 방법은 여러방법이 있겠지만 분할정복으로 풀고자 함을 밝힌다.

 

핵심은 ${i > j 인 i,j에 대해 arr_i > arr_j}$ 의 개수를 찾는 것이다.

먼저, 전체구간 [l,r] 을 구간 left = [ l, m ]  & right = [ m+1, r ] 로 분할을 해보자.

그렇게 분할을 계속하다가 분할된 구간[l, r]의 크기가 1일 때 분할을 멈추고 카운팅을 시작한다.

 

 

 

카운팅을 할 때, 오른쪽 구간에 있는 원소가 왼쪽 구간에 있는 원소보다 인덱스가 더 크다는 것은 자명하다. 그러므로, left 구간에 있는 원소와 right 구간에 있는 원소를 비교하여 right 구간의 원소보다 큰 left 구간의 원소를 더하는 것으로 구현은 가능하다.

하지만, left 와 right 가 정렬이 되어 있지 않은 상황에서 개수를 파악하는 방법은 right의 각각의 원소에 대해서 left구간을 전부 탐색을 해야하므로, Partitioning 을 하고 다시 카운팅을 하기 전에 각각의 left, right 부분집합들을 정렬해준다면 투 포인터 방식으로 인덱스를 옮겨가며 N시간만에 개수를 파악할 수 있다.

 

left, right 부분집합들이 정렬되어 있는 상태에서 카운팅을 하는 방법을 살펴보자.

 

초기 상태는 다음과 같다.

 

현재, i < j 이고 arr[i] 보다 arr[j] 가 더 작은 상태이므로 현재 arr[j]보다 크고 i < j 를 만족하는 arr[i] 가 2개 존재하므로 이것을 카운팅 변수에 더하고, 이 후 정렬된 새로운 집합(오름차순)에 arr[j]를 넣어준다. 그렇다면 다음과 같은 상태가 될 것이다.

 

이 후 동일하게 arr[i], arr[j]를 비교한다. 이 상황에서 arr[i] 가 arr[j] 보다 작으므로 더 작은 값을 "정렬된 새로운 집합"에 넣어주고 다음으로 넘어간다.

동일한 과정을 반복한다면, i 또는 j 가 범위를 벗어날 때 범위를 벗어나지 않는 쪽 인덱스 부터 끝까지 정렬된 새로운 집합에 넣어주는 것으로 부분 정렬과 동시에 카운팅을 수행할 수 있다.

 

전체적인 코드는 Merge Sort를 수행하는 과정에서 카운팅을 하는 부분만 추가하면 되는 구조이다.

 

총 시간복잡도는 ${O(NlogN)}$이다.

소스 코드

#include <bits/stdc++.h>
using namespace std;
vector<int> arr;
long long answer = 0;
void counting(int l, int m, int r){
    int i = l, j = m+1;
    int k = 0;
    vector<int> tmp(r-l+1);
    // 시간복잡도를 줄이기 위해
    while(i <= m && j <= r ){
        if( arr[i] > arr[j] ) {
            answer += ( m - i + 1 );
            tmp[k++] = arr[j];
            j += 1;
        }
        else{
            tmp[k++] = arr[i];
            i += 1;
        }
    }
    if( m < i ){
        while( j <= r )
            tmp[k++] = arr[j++];
    }
    else{
        while( i <= m )
            tmp[k++] = arr[i++];
    }
    for(int i=l, k=0; i<=r; i++){
        arr[i] = tmp[k++];
    }
}
void partition(int l, int r){
    if( l >= r )
        return;

    int m = (l+r)/2;

    partition(l, m);
    partition(m+1, r);

    counting(l, m, r);
}
// 부분 정렬 까지 수행해야하는 이유 ?? :
// 구간에서 개수를 카운팅하기 위한 시간복잡도 줄이기 위함, 정렬 x시 최대 N^2

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int N ;
    cin >> N;
    arr.resize(N);
    for(int i=0; i<N; i++)
        cin >> arr[i];

    partition(0, N-1);

    cout << answer ;


    return 0;
}