[PS] 공항 / C++ (백준 10775번)

 

 

문제를 읽고 생각해 보면 greedy 문제라는 것은 쉽게 알 수 있다. 하지만 매번 gi~1까지 빈 출구를 찾으면서 greedy 하게 도킹하게 되면 G, P <= 100,000 이므로 $O(n^2)$으로 시간 초과가 난다.

 

풀이 과정

분리 집합을 사용하여 그리디하게 출구들을 도킹시키면 $O(N)$만에 풀 수 있다. 도킹이 끝난 출구들이 연결되어 있을 때 한 집합으로 보고 연결해 준다.

• i번 출구를 도킹시켰을 때, i-1 출구가 비어있으면 새로운 집합(i-1이 도킹할 수 있는 가장 큰 번호의 출구인 집합)을 만들어준다.
• i-1 출구가 비어있지 않다면, i-1 출구의 집합에 포함시킨다.
• 1번 출구가 포함된 집합은 더 이상 포함될 집합(i-1이 0이기 때문)이 없기 때문에 1번 출구에 -1을 저장해 주고, union_find에서 이미 도킹된 1번 출구까지 내려오게 된다면 -1을 반환한 뒤, 도킹을 멈추고 답을 출력해 주면 된다.   
  1. 예를 들어 첫 도킹으로 3번 출구까지 도킹할 수 있는 비행기가 도킹될 때, 2번 출구(i-1 출구)가 비어있기 때문에 새로운 집합을 만들어주는 의미로 uni[3]에 2를 저장한다.
  2. 다음으로 4번 출구까지 도킹할 수 있는 비행기를 도킹할 때, 3번 출구(i-1출구)에 집합이 이미 있기 때문에 그 집합에 포함된다는 의미로 uni[3] 값을 uni[4]에 저장한다.
  3. 다음으로 4번 출구까지 도킹할 수 있는 비행기가 도킹된다면, 4번 출구는 이미 도킹이 되어있고, uni[4]에 2번 출구가 저장되어 있으므로 4번 출구가 포함된 집합엔 3번 출구까지 차있다는 사실을 확인할 수 있으며, 2번 출구에 도킹시킨다.
  4. 2번 출구에 도킹시키는 방법은 똑같이 1번 출구(i-1출구)가 비어있는지 확인하고 비어있다면 uni[2]에 1을 저장해서 집합 중 도킹할 수 있는 가장 큰 번호의 추구가 1이라는 사실을 저장하고, 비어있지 않다면 uni[2]에 uni[1] 값을 저장하여 1번 출구의 집합과 합쳐주면 된다.
  5. 이때, 1번 출구가 비어있지 않다면 -1이 저장될 것이고 다른 비행기가 본 집합에 도킹하려 하면 -1이 반환되면서 더 이상 도킹시킬 수 있는 출구가 없다는 사실을 알려줄 것이다.
  6. 이런 식으로 출구들을 더 이상 도킹시킬 출구가 없을 때까지 반복해 준다.

 

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

int uni[100001], pl[100001];

int union_find(int cur) {
	if (uni[cur] == 0)return cur;
	else if (uni[cur] == -1)return -1;
	uni[cur] = union_find(uni[cur]);
	return uni[cur];
}

int main()
{
	int g, p;
	scanf("%d %d", &g, &p);
	for (int i = 0; i < p; i++)scanf("%d", &pl[i]);
	int dap = p;
	for (int i = 0; i < p; i++) {
		int plane=pl[i];
		if (uni[plane] == 0) {
			if (plane == 1) {
				uni[plane] = -1;
				continue;
			}
			uni[plane] = union_find(plane - 1);
		}
		else {
			int cur = union_find(plane);
			if (cur == -1) {
				dap = i;
				break;
			}
			else {
				if (cur == 1)uni[cur] = -1;
				else uni[cur] = union_find(cur - 1);
			}
		}
	}
	printf("%d\n", dap);
	return 0;
}