[Baekjoon,10775] 공항

새로운 비행기가 들어올 때마다 비행기의 번호와 같은 게이트에 도킹한다. 그런데 이미 해당 게이트에 다른 비행기가 도킹된 경우 하나 낮은 번호에 도킹을 시도한다. 이 과정을 반복하는데 1번 게이트까지 실패한 경우 더 이상 도킹할 수 없는 것이다.

이를 $DisjointSet$을 이용하여 간단히 구현할 수 있다. 각각의 노드의 $parent$를 자기 자신으로 설정한 뒤 새로운 입력에 따라 $(자기 자신-1)$번 노드와 $merge$하여 다음에 가르킬 게이트를 설정하는 것이다. 구현된 코드를 아래에서 볼 수 있다.

#include <iostream>
#include <vector>
using namespace std;

const int MAX = 1e5 + 1;

struct Disjointset
{
	vector<int> parent;
	Disjointset(int n) : parent(n)
	{
		for (int i = 0;i < n;++i)
			parent[i] = i;
	}
	int find(int n)
	{
		if (n == parent[n])
			return n;
		return parent[n] = find(parent[n]);
	} 
	void merge(int a, int b)
	{
		a = find(a); b = find(b);
		if (a == b)
			return;
		if (a > b) swap(a, b);
		parent[b] = a;
	}
};

int g,p;
int airplane[MAX];

int solve()
{
	int ret = 0;
	Disjointset gates(g+1);
	for (int i = 0;i < p;++i)
	{
		int docking = gates.find(airplane[i]);
		// 도킹할 수 있는 게이트가 없는 경우
		if (docking == 0)
			break;
		gates.merge(docking, docking - 1);
		++ret;
	}
	return ret;
}

int main()
{
	cin >> g >> p;
	for (int i = 0;i < p;++i)
		cin >> airplane[i];

	cout << solve() << endl;

	return 0;
}