10775 airport

์•Œ๊ณ ๋ฆฌ์ฆ˜(์ž๋ฃŒ๊ตฌ์กฐ, ํŠธ๋ฆฌ๋ฅผ ์ด์šฉํ•œ ์ด์ง„ํƒ์ƒ‰)

1. ๊ฒŒ์ดํŠธ์˜ ๊ฐœ์ˆ˜์— ๋งž๊ฒŒ 1~G๋ฅผ set์— ๋„ฃ์Œ
2. boolํ˜• check ๋ฐฐ์—ด์—์„œ, gi์— ์•„๋ฌด๊ฒƒ๋„ ์—†์œผ๋ฉด gi์— ๋„ฃ๊ณ  set์—์„œ gi ์‚ญ์ œ
3. ์ด๋ฏธ gi์— ๋“ค์–ด๊ฐ€ ์žˆ์œผ๋ฉด, set์—์„œ upperbound๋กœ gi์ดˆ๊ณผํ•˜๋Š” ์ฒซ๋ฒˆ์งธ๋ฅผ ์ฐพ์Œ
		-> ๋งŒ์•ฝ ๊ทธ ์ฒซ๋ฒˆ์งธ๊ฐ€ begin()์ด๋ฉด ์—†๋Š” ๊ฒƒ -> false ๋ฐ˜ํ™˜ ํ›„ ์ž…๋ ฅ ์ข…๋ฃŒ
		-> begin()์ด ์•„๋‹ˆ๋ฉด ๊ทธ ๊ณณ์—์„œ ํ•œ์นธ ์•„๋ž˜์— ๋„ํ‚นํ•˜๊ณ , true๋ฐ˜ํ™˜

์ฃผ์˜์ 

1. set์˜ erase๋Š” iterator๋ฅผ ๋ฐ›๋Š”๋‹ค.

์ฝ”๋“œ

#include <iostream>
#include <set>
#define MAX 100001
 
using namespace std;
 
int numOfGate, numOfPlane, planeCount;
bool gate[MAX];
set<int> s;
 
//gateIndex์— ๋„ฃ์„ ์ž๋ฆฌ์— ๋„ฃ๊ธฐ
//๋„ฃ์„ ๊ณณ์€ ์ตœ๋Œ€ํ•œ ํฐ ๊ณณ์— ๋„ฃ๋Š”๊ฒŒ ์ข‹๋‹ค.
//๋”ฐ๋ผ์„œ 5๊ฐ€ ๋“ค์–ด์˜ค๋ฉด, gateIndex์—์„œ 5๋ฅผ ์กฐํšŒํ•ด์„œ, ๊ฐ€๋ฆฌํ‚ค๋Š” ์œ„์น˜์— ๋„ฃ๊ธฐ
//๊ฐ€๋ฆฌํ‚ค๋Š” ์œ„์น˜๋Š” ์ฒ˜์Œ์—” ์ž๊ธฐ์ž์‹ , ๊ทธ ํ›„์—” ๋„ฃ์–ด์งˆ๋•Œ๋งˆ๋‹ค 1์นธ์”ฉ ์•ž์œผ๋กœ ๋‹น๊ธฐ๊ธฐ.
//๋Œ€์‹  ๊ทธ ์•ž์— ๊ฒƒ๋„ ์ ์ ˆํžˆ ์กฐ์ ˆ
//ex) 5 5 5 ๊ณ„์† ๋“ค์–ด์˜ค๋ฉด, gateIndex๋Š” 1 2 3 4 5 6 -> 1 2 3 4 4 6-> 1 2 3 3 3 6-> 1 2 2 2 2 6-> 1 1 1 1 1 6-> 0  0 0 0 0 6-> 0์ž๋ฆฌ์—” ๋ชป๋„ฃ๊ฒŒ ํ•จ.
//1์”ฉ ์ค„์—ฌ์ฃผ๋Š”๊ณผ์ •์—์„œ ์‹œ๊ฐ„์ดˆ๊ณผ๊ฐ€ ๋œธ.
bool canPut(int max);
void makeSet();
 
int main() {
	cin >> numOfGate >> numOfPlane;
	makeSet();
	int temp;
	bool check = true;
	for (int i = 0; i < numOfPlane; i++) {
		cin >> temp;
		if (check && canPut(temp))
			planeCount++;
		else
			check = false;
	}
	cout << planeCount << endl;
 
}
 
void makeSet() {
	for (int i = 1; i <= numOfGate; i++)
		s.insert(i);
}
 
bool canPut(int max) {
	if (!gate[max]) {
		gate[max] = true;
		s.erase(s.find(max));
		return true;
	}
	else {
		set<int>::iterator iter = s.upper_bound(max);
		if (iter == s.begin())
			return false;
		else {
			iter--;
			gate[*iter] = true;
			s.erase(iter);
			return true;
		}
	}
}