백준10775 공항

작성일 | In

문제 링크

  • http://icpc.me/10775

문제 출처

  • 2015 CCC Senior Division 3번
  • 2018 IOI 여름학교 2일차 2번 문제

사용 알고리즘

  • Binary Search
  • set

시간복잡도

  • O((G+P) log G)

풀이

이 문제는 lower_bound나 upper_bound를 이용해 푸는 문제입니다.
G와 P가 최대 100,000이기 때문에 시간 복잡도는 O(N log N) 형태가 나와야 합니다.
자동으로 정렬해주고(정확히는 정렬된 결과를 보여주는) 삽입, 검색, 삭제가 모두 O(log N)에 가능한 자료구조 set을 쓸 것입니다.
이 문제의 해결하기 위해서는 비행기를 가능한 한 가장 큰 번호의 게이트에 도킹 시켜야 합니다.
풀이 순서를 알아봅시다.

  1. 1부터 G까지의 수를 set에 넣습니다. (모든 게이트를 set에 삽입, set에는 도킹 되지 않은 게이트를 저장)
  2. gi를 입력받습니다.
  3. set에서 gi를 검색합니다.
  4. set에서 gi를 찾은 경우에는 해당 데이터를 set에서 삭제합니다. (도킹 완료)
  5. set에 gi가 없는 경우에는 set.lower_bound(gi)로 검색합니다. 1. 만약 lower_bound의 반환 값이 set.begin() 이라면 도킹 가능한 게이트가 없으므로 현재까지 도킹 된 비행기의 수를 출력하고 프로그램을 종료합니다. 2. 만약 lower_bound의 반환한 위치의 바로 이전의 데이터가 gi보다 큰 경우에도 도킹 가능한 게이트가 없음을 의미하므로 현재까지 도킹 된 비행기의 수를 출력하고 프로그램을 종료합니다. 3. 나머지의 경우에는 도킹이 가능하므로 lower_bound의 반환 값을 set에서 삭제합니다. (도킹 완료)
  6. 2, 3번을 P번 반복합니다.
  7. 반복을 끝까지 수행했다는 것은 모든 비행기를 도킹했다는 것을 의미하므로 P를 출력하고 프로그램을 종료합니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int g, p; cin >> g >> p;
	set<int> s;
	for(int i=1; i<=g; i++) s.insert(i);
	for(int i=0; i<p; i++){
		int t; cin >> t;
		set<int>::iterator it = s.find(t);
		if(it != s.end()){
			s.erase(it);
			continue;
		}
		it = s.lower_bound(t);
		if(it == s.begin()){
			cout << i;
			return 0;
		}
		if(*(--it) > t){
			cout << i;
			return 0;
		}
		s.erase(it);
	}
	cout << p;
	return 0;
}