1927번: 최소 힙
접근 방법
입력 값이 들어올 때마다 최소한의 시간안에 정렬을 할 수 있는 자료구조인 힙을 사용합니다. C++ STL의 priority_queue를 사용하면 쉽게 해결할 수 있습니다.
코드
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
| #include <bits/stdc++.h>
#define endl '\\n'
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define SUBMIT
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
#ifndef SUBMIT
(void)!freopen("input.txt", "r", stdin);
cout << "# From the test case" << endl;
#endif
priority_queue<int, vector<int>, greater<int>> pq;
int x, n; cin >> n;
for(int i = 0; i < n; ++i) {
cin >> x;
if(x)
pq.push(x);
if(!x) {
if(pq.empty()) {
cout << 0 << endl;
continue;
}
cout << pq.top() << endl;
pq.pop();
}
}
return 0;
}
|