https://www.acmicpc.net/problem/7662
7662번: 이중 우선순위 큐
문제 이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또
www.acmicpc.net
stl에 있는 multiset을 사용하면 자동으로 정렬되기 때문에 쉽게 풀 수 있는 문제다.
set은 중복이 허용되지 않기때문에 multiset을 사용하여야한다.
|
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
|
#include <iostream>
#include <set>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
int k;
while (T--) {
multiset<int> ms;
cin >> k;
while (k--) {
char i;
int num;
cin >> i >> num;
if (i == 'I') {
ms.insert(num);
}
else if (i == 'D') {
if (ms.empty()) continue;
if (num == 1) {
//최댓값 삭제
ms.erase(--ms.end());
}
else {
//최솟값 삭제
ms.erase(ms.begin());
}
}
}
if (ms.empty()) cout << "EMPTY" << '\n';
else cout << *(--ms.end()) << ' ' << *ms.begin() << "\n";
}
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 10816. 숫자 카드 2 (0) | 2020.01.20 |
|---|---|
| [BOJ] 5567. 결혼식 (0) | 2019.11.13 |
| [BOJ] 17472. 다리 만들기 2 (0) | 2019.10.16 |
| [BOJ] 2146. 다리 만들기 (0) | 2019.10.16 |
| [BOJ] 17471. 게리맨더링 (0) | 2019.10.16 |