BOJ 10775 - 공항

문제

오늘은 신승원의 생일이다.

박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.

공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.

공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

입력

첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 10^5)가 주어진다.

두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 10^5)가 주어진다.

이후 P개의 줄에 gi (1 ≤ gi ≤ G) 가 주어진다.

출력

승원이가 도킹시킬 수 있는 최대의 비행기 수를 출력한다.

접근

문제에서 제시하는 게이트와 비행기의 최대 갯수는 10만개이다. 따라서, 최대 O(P * log(P))의 시간내에 문제를 해결해야 한다.
바꿔 말하면, 하나의 비행기를 도킹하는데 걸리는 최대 시간을 log(P) 혹은 log(G) 등의 시간으로 구현해야 한다.

i번째 비행기가 들어왔을때, 최선으로 도킹할수 있는 게이트는 gi와 가장 가까운, 그러니까 가장 큰 숫자의 게이트이다.
이 문제의 핵심은 그 게이트를 어떻게 빠른 방법으로 찾을 수 있는가이다.

다행히 좋은 알고리즘이 바로 생각났다. 바로 Union-Find이다.
각 게이트를 하나의 노드로 놓고, 처음엔 자기 자신으로 초기화를 해 놓은뒤, 가능한 가장 큰 숫자를 부모 노드로 초기화시키면서 도킹을 진행하면, 각 도킹이 O(1)의 시간내로 가능하다. 물론 업데이트도 마찬가지이다.

풀이

Union-Find로 접근을 완료했다면, 고려해야될 것은 크게 없다.
각 게이트의 parent를 자기 자신으로 초기화 시킨 뒤, 비행기가 들어올 때 마다 find 과정을 거친다. 이 때, find로 나온 값이 0이면 도킹할 수 있는 게이트가 없다는 의미이므로, 반복문을 탈출해도 된다.
find가 종료되면 해당 게이트가 docking 변수에 저장되는데, 이 docking 게이트에 이번 비행기를 도킹시킬 것이므로, docking - 1 값과 merge 시켜서 사용중 상태로 만든다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int

int G, P;
int parent[100001];
int answer = 0;

int find(int num)
{
	if (num == parent[num]) return num;
	return parent[num] = find(parent[num]);
}

void merge(int u, int v)
{
	u = find(u);
	v = find(v);
	parent[u] = v;
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> G >> P;
	for (int i = 1; i <= G; i++) parent[i] = i;
	while (P--)
	{
		int temp;
		cin >> temp;
		int docking = find(temp);
		if (docking)
		{
			merge(docking, docking - 1);
			answer++;
		}
		else break;
	}
	cout << answer;

	return 0;
}