[PS] 2013 Daejeon 6508 Permutation Graphs

Permutation Graphs 란 구글에 치면 본 문제와 같은 그림이 많이 나온다.

원소의 개수와 원소의 내용이 같은데, 순서만 다른 두 배열을 주고

같은 원소끼리 선을 긋고

겹치는 선이 생기는 원소끼리 간선을 이어준 그래프이다.

문제는 위의 두 배열만을 주어주고, 그래프를 만들었을때

총 몇개의 간선이 생기냐?를 묻는 문제이다.

주먹구구식으로O(n^2) 으로 풀수도 있지만

당연히 Time Limit 가 뜬다.

본 문제는 Binary Index Tree를 사용하는 문제이며

풀이는 조금 어렵지만 다음과 같다.

위의 그림에서 배열은 다음과 같다.

[2,5,4,1,3]
[1,5,3,2,4]

위의 2가 0번째에 있고, 아래의 2가 3번째에 있다.

그럼 2와 겹치는 선은 무조건 3개이다.

(아래의 2 앞에 3개의 숫자가 있고, 위의 나머지 숫자는 모두 2의 오른쪽에 있으므로)

그리고 2를 제거하면된다.

하지만 배열이나 리스트던 뭐던 제거를 하면 시간이 걸리므로...

제거된 숫자를 Binary index tree에 추가한다.

2가 3번째에 있으므로, 4번째에 제거된 카운트 1을 Add 한다.

(이진 인덱스 트리는 0번째부터 시작하지 않음)

[0 0 0 1 0] 과 같이 된다. 5가 끝이므로

그리고 5를 보면 아래의 5는 1번째에 있다. 그리고 아래의 5의 왼쪽에 2가 있으면

5는 0개와 겹치고, 왼쪽에 2가 없으면 1개와 겹친다.

BIS에서 제거된 인덱스 번호가 4이므로.... 2까지의 합을 구해보면 된다.

2까지의합은 보나마나 0이고, 5와 겹치는 선은 1개이다. ( 아까 2와 겹친건 제외)

이런식으로 계산하면 nlogn 시간에 본 문제를 풀 수 있다.