반응형
방법 1. priority queue 두개 사용 (양수 / 음수)
방법 2. pair<int, int> 사용
방법 3. 정렬을 위한 cmp 구조체 사용
1. priority 두개 사용
|
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
|
#include <iostream>
#include <queue>
using namespace std;
priority_queue<int, vector<int>, greater<int> > pq_pos;
priority_queue<int> pq_neg;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
for (int i = 0;i < n;i++) {
int x;
cin >> x;
if (x == 0) {
if (pq_pos.empty()) {
// 1. 둘 다 비었음
if (pq_neg.empty())
cout << 0 << '\n';
// 2. 양수pq (x), 음수pq(o)
else {
cout << pq_neg.top() << '\n';
pq_neg.pop();
}
}
else {
// 3. 양수pq (o), 음수pq(x)
if (pq_neg.empty()) {
cout << pq_pos.top() << '\n';
pq_pos.pop();
}
// 4. 둘 다 있음
else {
if (pq_pos.top() < -pq_neg.top()) { // 2 vs -3: 양수 출력
cout << pq_pos.top() << '\n'; // 2 vs -2: 음수 출력
pq_pos.pop(); // 2 vs -1: 음수 출력
}
else {
cout << pq_neg.top() << '\n';
pq_neg.pop();
}
}
}
}
else {
if (x > 0)
pq_pos.push(x);
else
pq_neg.push(x);
}
}
}
|
cs |
2. pair<int, int> 사용
정렬 기준
1순위: 첫 번째 (절대값)
2순위: 두 번째 (원래값)
(2, -2) (1, -1)
(1, -1) (1, 1)
(1, 1) -> (2, -2)
(2, 2) (2, 2)
|
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
|
#include <iostream>
#include <queue>
#define pii pair<int, int>
using namespace std;
priority_queue<pii, vector<pii>, greater<pii> > pq;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
for (int i = 0;i < n;i++) {
int x;
cin >> x;
if (x == 0) {
if (pq.empty())
cout << 0 << '\n';
else {
cout << pq.top().second << '\n';
pq.pop();
}
}
else {
pq.push({ abs(x), x });
}
}
}
|
cs |
3. 정렬을 위한 cmp 구조체 사용
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 | #include <iostream> #include <queue> using namespace std; struct cmp { bool operator()(int a, int b) { if (abs(a) == abs(b)) return a > b; return abs(a) > abs(b); } }; priority_queue<int, vector<int>, cmp > pq; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; for (int i = 0;i < n;i++) { int x; cin >> x; if (x == 0) { if (pq.empty()) cout << 0 << '\n'; else { cout << pq.top() << '\n'; pq.pop(); } } else { pq.push(x); } } } | cs |
반응형
'백준 > 우선순위큐' 카테고리의 다른 글
| 백준 1655 [복습필수] (0) | 2021.07.11 |
|---|