[백준] 7578: 공장[Java]

 

 

 

알고리즘 분류: 세그먼트 트리, 자료구조

문제 링크: https://www.acmicpc.net/problem/7578

 

 

 

---

 

 

어떻게 풀어야 할까.. 막막하지만

역전(inversion) 이라는 개념을 알고 있으면 정말 쉬워진다.

역전(inversion)은 배열에서 앞에 있는 값이 뒤에 있는 값보다 큰 경우를 말하기도 하고,
원본 배열과 비교 배열에서 원본 배열의 요소가 비교 배열의 요소에서 얼마나 뒤로 떨어져 있는지를 의미하기도 한다.

 

풀이는 굉장히 간단한데, 그냥 inversion된 애들이 얼마나 inversion 되었는지 세어주면 된다.

 

어차피 모든 요소들이 매칭이 되어야하므로

어떤 요소가 inversion 되지 않았다면(뒤에 위치하고 있다면)?

어떤 요소는 반드시 inversion 되어 있는 상태가 된다.

 

위 그림의 경우 A 배열에서 392는 -1 만큼

351이 -2 만큼 inversion이 일어났으므로 이 예제는 3이 되는 것

 

다만 N이 500000개 까지 주어지므로 inversion 갯수를 세는 로직을 O(n log n)으로 처리해야 하는데,

이는 병합 정렬과 세그먼트 트리로 처리할 수 있다.

병합 정렬은 두 분할된 배열의 병합 과정에서의 inversion 갯수가 버블 소트의 스왑 횟수와 같다는 점을 이용,

세그먼트 트리는 특정 구간의 inversion 수를 구하는 쿼리를 짜서 이용한다.

 

본 글은 세그먼트 트리로 구현했다.

로직은 첫번째 배열 값이 두번째 배열의 어느 위치에 있는지 찾고 그 위치 이후의 inversion 횟수를 더해 해결하면 된다.

 

---

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static class SegTree{
        long[] tree;
        int size;
        SegTree(int n){
            tree=new long[n*4];
            size=n;
        }
        void update(int node,int start,int end,int idx){
            if(end<idx||idx<start)return;
            if(start==end){
                tree[node]++;
                return;
            }
            int mid=(start+end)>>1;
            update(node<<1,start,mid,idx);
            update(node<<1|1,mid+1,end,idx);
            tree[node]=tree[node<<1]+tree[node<<1|1];
        }
        long query(int node,int start,int end,int left,int right){
            if(right<start||end<left)return 0;
            if(left<=start&&end<=right)return tree[node];
            int mid=(start+end)>>1;
            return query(node<<1,start,mid,left,right)+
                    query(node<<1|1,mid+1,end,left,right);
        }
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        int n=Integer.parseInt(br.readLine());
        int[] a=new int[n+1];
        int[] b=new int[n+1];
        int[]bpos=new int[1000001];

        st=new StringTokenizer(br.readLine());
        for(int i=1;i<=n;i++) {
            a[i]=Integer.parseInt(st.nextToken());
        }
        st=new StringTokenizer(br.readLine());
        for(int i=1;i<=n;i++) {
           b[i]=Integer.parseInt(st.nextToken());
           bpos[b[i]]=i;
        }
        SegTree t=new SegTree(n);
        long inversion=0;
        for(int i=1;i<=n;i++){
            int idx=bpos[a[i]];
            inversion+=t.query(1,1,n,idx+1,n);
            t.update(1,1,n,idx);
        }
        System.out.println(inversion);
    }
}