10775 airport
알고리즘(자료구조, 트리를 이용한 이진탐색)
1
2
3
4
5
1. 게이트의 개수에 맞게 1~G를 set에 넣음
2. bool형 check 배열에서, gi에 아무것도 없으면 gi에 넣고 set에서 gi 삭제
3. 이미 gi에 들어가 있으면, set에서 upperbound로 gi초과하는 첫번째를 찾음
-> 만약 그 첫번째가 begin()이면 없는 것 -> false 반환 후 입력 종료
-> begin()이 아니면 그 곳에서 한칸 아래에 도킹하고, true반환
주의점
1
1. set의 erase는 iterator를 받는다.
코드
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#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;
}
}
}