[백준]7578 공장 #세그먼트트리

1. 풀이

A열에 있는 기계들을 왼쪽부터 차례대로 B와 매칭시킨다.

이때 매칭된 B의 오른쪽에 있는 기계중에 매칭된 기계의 수가 겹치는 선의 수가 된다.

그 이유는, A의 왼쪽기계부터 차례대로 매칭을 시키기 때문에, B의 왼쪽 기계는 매칭이 되었어도 선이 겹칠일이 없기 때문이다.

이를 그림으로 표현하면 아래와 같다.

 

따라서 예시를 순서대로 진행하면 아래와 같다.

따라서 답(겹치는 선의 수)은 3이다.

 

이때 수행해야 할 작업은 아래와 같이 두가지이고 각각을 다음과 같이 해결한다.

(1) 현재 매칭중인 기계의 B에서의 위치 => dictionary 자료형 이용

(2) B의 오른쪽에서 이미 매칭이 된 기계의 개수 => 세그먼트트리(구간합) 이용

 

2. 소스코드

import math
import sys

N=int(input())
A=[0]+list(map(int,sys.stdin.readline().rstrip().split()))
B=[0]+list(map(int,sys.stdin.readline().rstrip().split()))
BDic={}
for i in range(1,N+1):
    BDic[B[i]]=i

def treeSum(node,start,end,left,right):
    if left<=start and end<=right:
        return tree[node]
    elif right<start or end<left:
        return 0
    else:
        mid=(start+end)//2
        return treeSum(node*2,start,mid,left,right)+treeSum(node*2+1,mid+1,end,left,right)

def update(node,start,end,index):
    if not start<=index<=end:
        return

    tree[node]+=1
    if start==end:
        return

    mid=(start+end)//2
    update(node*2,start,mid,index)
    update(node*2+1,mid+1,end,index)


size=2**(math.ceil(math.log(N,2))+1)
tree=[0 for i in range(size)]
ans=0

for i in range(1,N+1):
    num=A[i]
    index=BDic[num]
    ans+=treeSum(1,1,N,index+1,N)
    update(1,1,N,index)

print(ans)