[G2] 백준 10775번 공항 C++ 그리디 알고리즘, set, 이진 탐색

리뷰

 

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

set과 upper_bound를 활용한 그리디 문제

 

 

전역 변수

1. g : 게이트의 수를 저장할 변수
2. p : 비행기의 수를 저장할 변수
3. ans : 정답을 저장할 변수
4. dic : 게이트의 상태를 저장할 정수형 집합

 

함수

없음

 

 

문제풀이

1. g, p에 값을 입력 받고, dic에 1 ~ g까지의 정수를 insert해준다.
2. p번의 while루프를 개행해 주고, 매 루프마다 게이트 번호를 입력 받아준다.
3. upper_bound 함수를 통해 dic에서 gate보다 큰 값의 이터레이터를 it에 저장해 준다.
4. 만약 it이 dic의 begin이라면 ans를 출력하고 main함수를 리턴해 준다.
5. 아니라면 dic에서 it의 앞쪽 데이터를 erase처리해 주고, ans를 1만큼 증가시켜 준다.
6. 탐색이 종료될 때 까지 main함수가 return되지 않았다면 ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• upper_bound를 통해 x보다 큰 값을 구하고 이터레이터를 감소시키면 x보다 작은 값 중 최대값을 구할 수 있다.
• 다만, 이터레이터가 자료구조의 begin이라면 x보다 작은 값이 존재하지 않는 것이다.
• set은 레드-블랙 트리 기반의 정렬된 자료구조이며, insert, upper_bound, erase모두 LogN의 시간 복잡도를 가진다.

 

정답 코드

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

int g, p, ans;
set<int> dic;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> g >> p;
	for (int i = 1; i <= g; ++i) dic.insert(i);
	while (p--) {
		int gate; cin >> gate;
		auto it = dic.upper_bound(gate);
		if (it == dic.begin()) {
			cout << ans;
			return 0;
		}
		else {
			dic.erase(--it);
			ans++;
		}
	}
	cout << ans;
}