[백준] 10775. 공항

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

10775번: 공항

로직 자체는 떠올리기 쉬웠다.

 

i번째 비행기가 1~g_i 까지 도킹할 수 있을 때, g_i부터 차례대로 보면서 자리가 남아있으면 채우면 된다. 즉, 도킹할 수 있는 구간중 게이트 번호가 가장 큰 수를 먼저 고르면 가장 많은 비행기를 도킹할 수 있다.

 

만약 그렇지 않으려면, 다른 순서로 도킹하는 방법이 위 방법보다 더 많은 비행기를 도킹시킬 수 있음을 보이면 된다.

도킹을 주어진 구간(1~g_i)에서 가장 작은 것부터 채워나간다고 해보자. 이때 주어진 입력이 다음과 같다고 하면

2
2
2
1

가정한 방법은 1대의 비행기밖에 도킹시키지 못하지만, 위에 제시한 방법은 2대를 도킹시킬 수 있다.

---

처음에는 위 로직만 가지고 구현하려 했다.

구간이 주어질 때마다, 입력으로 들어온 수부터 차례대로 수를 줄여가면서 도킹되지 않은 게이트를 찾아갔다.

문제는 이 방법이 TLE가 나는데, 입력으로 들어오는 게이트 수(G)의 최댓값은 100,000이고 도킹되지 않은 게이트를 찾는 부분은 시간 복잡도가 O(G)이기 때문에 최악의 경우 O(G²)가 된다. 그래서 시간초과로 한 번 틀렸다.

 

이제 도킹되지 않은 게이트를 찾는 부분의 시간복잡도를 줄여야하는데, 도저히 아이디어가 떠오르지 않아서 찾아보니 두가지 방법이 나왔다.

1. std::set::lower_bound를 사용하는 방법

set을 잘 사용하지 않아서 몰랐는데, 트리구조로 구현이 되어있고 삽입시 자동으로 정렬이 된다고 한다. 따라서 lower_bound도 사용할 수 있는데, 왜 lower_bound를 사용해야 할까?

 

이유는 도킹되지 않은 게이트 중에서 가장 번호가 큰 부분부터 채워야하기 때문이다. lower_bound는 찾고자 하는 값 이상인 값을 찾기 때문에 만약 lower_bound로 찾은 값이 찾고자 했던 게이트 번호와 일치한다면 도킹시키면 된다. 그렇지 않은 경우 두가지 상황이 벌어질 수 있다.

 

첫번째는 set.begin()이 리턴된 경우이다.

찾고자 하는 게이트 번호가 set에 존재하는 값들 중 가장 작은 값보다도 작다는 의미이다. 즉, 더이상 도킹할 수 있는 비행기가 없다.

 

두번째는 set.end()가 리턴된 경우이다.

찾고자하는 게이트 번호가 set에 존재하는 값들 중 가장 큰 값보다 더 크다는 의미이다. 이는 아직 도킹할 수 있는 가능성이 있는데, 이유는 찾으려는 게이트 번호보다 작은 번호를 가진 게이트들 중 아직 도킹되지 않은 게이트가 있을 수 있기 때문이다.

이때는 반환된 iterator의 바로 이전 iterator를 역참조 해본 값을 보면 된다. 그 값이 찾고자 하는 번호보다 작다면 도킹하고, 더 크다면 이미 찾으려는 게이트 번호보다 작은 게이트 들은 도킹되었으므로 도킹할 수 있는 게이트 번호가 없다는 뜻이 된다.

 

따라서 이를 고려해 코드를 작성하면 다음과 같다.

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

int G, P;
set<int> s;

int main() {
	cin >> G >> P;
	for(int i=1; i<=G; i++) s.insert(i);
	
	set<int>::iterator iter;
	
	int ret = 0;
	for(int i=0; i<=G; i++) {
		int f;
		cin >> f;
		
		iter = s.lower_bound(f);
		if(*iter == f) {
			ret++;
			s.erase(iter);
			continue;
		}
		if(iter == s.begin()) break;
		if(*(--iter) > f) break;
		
		s.erase(iter);
		ret++;
	}
	
	cout << ret << "\n";
}

 

2. Union-Find(Disjoint-set) 사용

이 아이디어를 바로 떠올린 사람은 천재일지도 모른다.

 

먼저 배열을 만든다. 이때 게이트 숫자보다 1 크게 만든다. 각 배열의 값들은 인덱스와 같도록 해둔다. 이 배열의 의미하는 것은 해당 게이트 이하의 게이트 중 도킹할 수 있는 게이트의 최댓값이다.

 

x 번째 게이트 번호를 찾을 때(gate[x]) 그 값이 x와 같다면 도킹한 후, gate[x]의 값을 gate[x-1]과 같게 만들어준다.

만약 gate[x-1]이  x-1과 같다면 x-1이하의 게이트는 모두 사용할 수 있음을 의미하고, 만약 gate[x-1]이 x-1과 같지 않다면 이미 그 게이트도 사용되었음을 의미한다. 이렇게 되면 비행기가 들어오면 들어올 수록 배열의 값들은 0이 된다. 즉, 그 번호 이하의 게이트는 사용할 수 없음을 의미한다.

 

이를 union-find로 구현한다. 게이트 번호를 찾을 때는 find함수를 사용하고, 만약 찾았다면 (검색했던 게이트 번호 - 1)과 병합하기 위해 merge 함수를 사용하면 된다.

 

다음은 위 내용을 구현한 코드이다.

#include <iostream>
using namespace std;

const int MAX_N = 1e5 + 1;
int G, P;
int par[MAX_N];

int find(int x) {
	if(x == par[x]) return x;
	return par[x] = find(par[x]);
}

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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> G >> P;
	
	for(int i=0; i<=G; i++) par[i] = i;
	
	int ret = 0;
	for(int i=0; i<P; i++) {
		int p;
		cin >> p;
		
		int doc = find(p);
		if(doc) {
			merge(doc, doc-1);
			ret++;
		} else break;
	}
	
	cout << ret << "\n";
}