[BOJ 10775] 공항

풀이

처음에는 세그먼트 트리를 이용하여 풀려고 했지만 비어있는 게이트를 찾는 과정에서 처리를 잘하지 못하여 시간초과가 발생하였다 그래서 여러 풀이를 참조하여 Union-Find를 이용하여 풀이함. 각 게이트에서 이전 게이트들의 비어있는 개수를 가진 parent배열을 계속 갱신하면서 비어있는 게이트 개수가 0이면 현재 인덱스를 출력하였다.

코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cmath>
#include <fstream>

using namespace std;

int G,P;
vector<int> parent(100001);
int Find(int x) {
	if (parent[x] == x) return x;
	else {
		parent[x] = Find(parent[x]);
		return parent[x];
	}
}

void merge(int x, int y) {
	x = Find(x);
	y = Find(y);
	parent[x] = y;
}

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cin >> G >> P;
	for (int i = 1; i <= G; i++) parent[i] = i;

	int ans = 0;
	for (int i = 0; i < P; i++) {
		int x;
		cin >> x;

		int gate = Find(x);
		if (gate == 0) break;
		merge(gate, gate - 1);
		ans++;
	}
	cout << ans;



	return 0;
}