공항

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

10775번: 공항

 

1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 도킹

 

set<int>::iterator it = s.find(t);

 

값이 있다면 -> s.erase(it);

 

값이 없다면? lower_bound

 

불가능한 경우 2가지

1. t 보다 큰 값의 위치가 s.begin()

2. t 보다 큰 값의 위치의 앞이 t 보다 큼

*(--it) > t

 

<소스 코드>

#include <iostream>
#include <set>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    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에 gi가 있는지 find
        set<int>::iterator it = s.find(t);
 
        // set에 gi가 있는 경우
        if (it != s.end())
        {
            s.erase(it);
            continue;
        }
 
        // t 이상의 값이 발견되는 위치
        it = s.lower_bound(t);
 
        // 발견되는 위치가 s의 시작
        // 1 ~ gi까지 이므로 없다는 의미
        // 현재까지 도킹된 비행기 수 출력하고 종료
        if (it == s.begin())
        {
            cout << i;
            return 0;
        }
 
        // *(--it)는 t 이상의 값의 앞
        // 그 값이 t보다 크다면 없다는 의미
        if (*(--it) > t)
        {
            cout << i;
            return 0;
        }
 
 
        // 나머지 경우는 가능
        // 예를 들어 t가 5
        // *it가 6이고 *(--it)가 3이면
        // 넣을 수 있음
        s.erase(it);
    }
 
    // 반복문을 모두 통과했다면
    cout << p;
    return 0;
}