[BOJ/Platinum 5] 백준 4442 빌보의 생일(C++)

문제 링크

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

4442번: 빌보의 생일

 

문제

프로도와 샘은 다가오는 빌보의 111번째 생일 파티를 계획하려고 한다. 그들은 중간계의 모든 호빗을 생일 파티에 초대했고, 단 한 명의 예외도 없이 모두 참석하기로 했다. 호빗은 한 줄로 되어있는 매우 긴 식탁에 앉을것이다. 그러나, 프로도와 샘은 서로 대화를 하지 않으면서 파티를 계획했기 때문에, 각자 독자적으로 좌석표를 작성했다.

결국 프로도와 샘은 새로운 좌석표를 만들기로 했다. 이때, 새로운 좌석표와 두 좌석표에서 다른 순서로 앉은 쌍의 수를 최소로 하려고 한다. 이 값을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 호빗의 수를 나타내는 정수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 2개의 줄은 각각 프로도의 좌석표와 샘의 좌석표이다. 각 좌석표는 한 줄로 이루어져 있고, N개의 서로 다른 알파벳 문자열로 이루어져 있다. 두 좌석표에 등장하는 호빗의 이름은 모두 같다. 입력의 마지막 줄에는 0이 있다. 이름은 최대 6글자이다.

출력

각 테스트 케이스에 대해서, 최종 좌석표와 프로도와 샘의 좌석표에서 서로 다른 순서로 앉은 쌍의 최솟값을 출력한다.

예제 입력 1

3
Frodo Sam Bilbo
Sam Frodo Bilbo
5
A B C D E
B A D E C
0

예제 출력 1

1
3

알고리즘 분류

• 자료 구조

풀이

이 문제와 유사한 Inversion Counting 문제이다.

7578번: 공장

프로도의 좌석표를 기준으로 하고, 샘의 좌석표에서 프로도의 좌석표의 i번째 사람보다 앞에 있는 사람들 중에 프로도의 좌석표에서의 번호가 더 높은 사람, 그러니까 i보다 큰 번호를 가진 사람들의 수를 구한다.

코드

#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 1000001
#define LL long long
#define INF 1e9

using namespace std;
int N;
map<string, int> M;
vector<int> SegTree;
LL answer;

void Init() {
	M.clear();
	SegTree.clear();
	int Tree_Height = (int)ceil(log2(N));
	int Tree_Size = (1 << (Tree_Height + 1));
	SegTree.resize(Tree_Size);
	answer = 0;
}

void Update_SegTree(int Node, int S, int E, LL Val, LL Diff) {
	if (S == E) {
		SegTree[Node] += Diff;
		return;
	}
	int M = (S + E) / 2;
	if (Val <= M) {
		Update_SegTree(Node * 2, S, M, Val, Diff);
	}
	else {
		Update_SegTree(Node * 2 + 1, M + 1, E, Val, Diff);
	}
	SegTree[Node] = SegTree[Node * 2] + SegTree[Node * 2 + 1];
}

LL Find_Value(int Node, int S, int E, int Left, int Right) {
	if ((S > Right) || (Left > E)) {
		return 0;
	}
	if ((Left <= S) && (E <= Right)) {
		return SegTree[Node];
	}
	int M = (S + E) / 2;
	return Find_Value(Node * 2, S, M, Left, Right) + Find_Value(Node * 2 + 1, M + 1, E, Left, Right);
}

void Find_Answer() {
	cout << answer << "\n";
}

void Input() {
	while (1) {
		cin >> N;
		if (N == 0) {
			break;
		}
		Init();
		int IDX = 1;
		for (int i = 0; i < N; i++) {
			string Name;
			cin >> Name;
			M.insert(make_pair(Name, IDX++));
		}
		for (int i = 0; i < N; i++) {
			string Name;
			cin >> Name;
			answer += (M[Name] - 1) - Find_Value(1, 1, N, 1, M[Name] - 1);
			Update_SegTree(1, 1, N, M[Name], 1);
		}
		Find_Answer();
	};
}

int main() {
	FASTIO
	Input();

	return 0;
}