[BOJ - JAVA] 백준 10090번: Counting Inversions

Problem

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

10090번: Counting Inversions

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.

Input

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.

 

Output

Write the count of inversions on the standard output.

---

문제 해결 과정

Inversion Counting이라고도 알려진 나름 유명한 문제이다.

 

What is Inversion? 

  임의의 길이가 N인 정수 배열 A가 주어졌을 때, A의 index의 쌍 (i, j)에 대하여 i < j, A[i] > A[j]이면 (i, j)는 A의 Inversion이라고 한다.

 

접근 1 - Brute Force Algorithm

 

   2개의 for loop을 구성하여 outer loop 값보다 큰 inner loop의 값이 존재하는 경우를 counting한다. 

  이때 시간복잡도는 O(n²)가 된다. -> TLE 발생 ( 2≤ n ≤ 1000000)

   따라서 O(n²)보다 효율적인 복잡도를 갖는 알고리즘이 필요하다!!

 

접근 2 - Divide and Conquer

 

 어느 한 배열에서 inversion의 경우를 생각해보면 아래의 그림과 같이 정렬을 하는 과정에서 생기는 교차 점의 개수로 표현이 가능하다.

정렬 과정에서 서로 교차하는 경우의 수

따라서 Merge Sort 과정 중 merge 부분에서 arr[i] > arr[j] 인 경우를 count해주면  O(NlogN)의 시간 복잡도로 구할 수 있다. 

Inversion Counting in Merge Sort

---

My Solution Code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ10090 {
    static int[] tmp;
    static int[] arr;
    static long inversion;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N  = Integer.parseInt(br.readLine());   // 순열 길이
        arr = new int[N];
        tmp = new int[N];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        inversion = 0;

        mergeSort(0, N-1);

        System.out.println(inversion);
    }

    // divide and conquer
    static void mergeSort(int start, int end) {
        if (start >= end)   // 끝까지 분할 한 경우
            return;

        int mid = (start + end) >> 1; // 중앙 값
        mergeSort(start, mid);  // 좌측 (divide)
        mergeSort(mid+1, end);  // 우측 (divide)
        merge(start, end);  // 병합 (conquer)
    }

    static void merge(int left, int right) {
        int mid = (left + right) >> 1;
        int leftIdx = left;     // 좌측 배열 탐색 인덱스
        int rightIdx = mid+1;   // 우측 배열 탐색 인덱스
        int tempIdx = left;     // 임시 저장 배열 인덱스

        while (leftIdx <= mid && rightIdx <= right) {
            if(arr[leftIdx] <= arr[rightIdx]) {
                tmp[tempIdx++] = arr[leftIdx++];
            } else {
                // inversion 발생 경우 (leftIdx < rightIdx && arr[leftIdx] > arr[rightIdx] )
                tmp[tempIdx++] = arr[rightIdx++];
                inversion += (mid - leftIdx + 1);   // 교차점 count
            }
        }

        // 좌측 잔여 원소 배치
        while(leftIdx <= mid) {
            tmp[tempIdx++] = arr[leftIdx++];
        }

        // 우측 잔여 원소 배치
        while(rightIdx <= right) {
            tmp[tempIdx++] = arr[rightIdx++];
        }

        // copy array
        for(int i = left; i<=right; i++) {
            arr[i] = tmp[i];
        }
    }
}