[BOJ/Platinum 5] 백준 9463 순열 그래프(C++)

문제 링크

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

9463번: 순열 그래프

 

문제

그래프 G는 정점의 집합 V와 간선의 집합 E로 이루어져 있고, G = (V, E)로 나타낸다. 대부분의 경우에 V와 E는 명시되어 있다. 일부 그래프의 경우에는 집합이 명시되어 있지 않다. 예를 들어, 순열 그래프는 간선의 집합이 명시되어 있지 않다.

{1, 2, 3, 4, 5}로 이루어진 두 순열 (2, 5, 4, 1, 3)과 (1, 5, 3, 2, 4)가 있다. 평행선을 그리고, 그 위에 순열에 적힌 숫자 순서대로 정점을 그린다. 그 다음 같은 숫자끼리 선분을 연결한다. 아래 그림과 같이 교차하는 선분의 쌍은 총 여섯 개라는 것을 알 수 있다.

교차하는 쌍은 순열 그래프의 간선이 된다. 순열 그래프의 정점은 숫자가 되고, 간선은 교차하는 쌍이 된다. 위의 예를 이용해 순열 그래프를 만들면 V = {1, 2, 3, 4, 5}, E = {(1,2), (1,4), (1,5), (2,3), (2,5), (3,4)}. 위의 두 순열을 이용해 순열 그래프를 그리면 아래 그림과 같이 된다.

{1, 2, ..., n}으로 이루어진 두 순열이 주어졌을 때, 두 순열을 이용해 만든 순열 그래프의 간선의 개수를 구하는 프로그램을 작성하시오. 예를 들어, (2, 5, 4, 1, 3)과 (1, 5, 3, 2, 4)로 만든 순열 그래프의 간선의 개수는 6개이다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n이 주어진다. 둘째 줄과 셋째 줄에는 두 순열이 주어진다. 순열은 {1, 2, ..., n}으로 이루어져 있고, 공백으로 구분되어져 있다. (1 ≤ n ≤ 100,000)

출력

각 테스트 케이스 마다, 입력으로 주어진 두 순열로 만든 순열 그래프의 간선의 개수를 출력한다.

예제 입력 1

3
5
2 5 4 1 3
1 5 3 2 4
7
5 6 7 1 2 3 4
5 6 7 1 2 3 4
7
1 5 3 4 2 7 6
7 1 5 3 4 2 6

예제 출력 1

6
0
5

알고리즘 분류

• 자료 구조

풀이

이 문제와 비슷한  Inversion Counting 문제이다.

7578번: 공장

동일하게 map을 사용하여 첫 번째 순열을 저장하였지만 시간 제한에 걸려 그냥 배열로 바꿔서 해결하였다. (map을 clear하는 과정에서 시간을 더 쓰는 것 같은데 왜 그런지는 잘 모르겠다.)

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 100001
#define LL long long
#define INF 1e9

using namespace std;
int T, N;
int A[MAX];
int B[MAX];
int SegTree[MAX * 4 + 1];
LL answer;

void Init() {
	for (int i = 0; i < MAX; i++) {
		A[i] = 0;
		B[i] = 0;
	}
	for (int i = 0; i < (MAX * 4 + 1); i++) {
		SegTree[i] = 0;
	}
	answer = 0;
}

void Update(int Node, int S, int E, int V) {
	if (S == E) {
		SegTree[Node] += 1;
		return;
	}
	int Mid = (S + E) / 2;
	if (V <= Mid) {
		Update(Node * 2, S, Mid, V);
	}
	else {
		Update(Node * 2 + 1, Mid + 1, E, V);
	}
	SegTree[Node] = SegTree[Node * 2] + SegTree[Node * 2 + 1];
}

int Query(int Node, int S, int E, int L, int R) {
	if ((R < S) || (L > E)) {
		return 0;
	}
	if ((L <= S) && (E <= R)) {
		return SegTree[Node];
	}
	int Mid = (S + E) / 2;
	return Query(Node * 2, S, Mid, L, R) + Query(Node * 2 + 1, Mid + 1, E, L, R);
}

void Find_Answer() {
	for (int i = 1; i <= N; i++) {
		answer += (B[i] - 1) - Query(1, 1, N, 1, B[i]);
		Update(1, 1, N, B[i]);
	}
	printf("%lld\n", answer);
}

void Input() {
	scanf_s("%d", &T);
	while (T--) {
		scanf_s("%d", &N);
		Init();
		for (int i = 1; i <= N; i++) {
			int X;
			scanf_s("%d", &X);
			A[X] = i;
		}
		for (int i = 1; i <= N; i++) {
			int X;
			scanf_s("%d", &X);
			B[i] = A[X];
		}
		Find_Answer();
	};
}

int main() {
	FASTIO
	Input();

	return 0;
}