문제
https://www.acmicpc.net/problem/7662
문제해설
우선순위 큐를 deque처럼 데이터를
앞에서도 빼고 뒤에서도 뺄 수 있게 만들어야 한다.
그리고 그 안의 데이터는 정렬되어있어야 한다.
삽입명령과 삭제명령들이 주어지며
모든 명령들을 수행하고 난 뒤 남은 데이터의 최대값과 최소값을 출력한다.
문제풀이
자료구조 중 하나인 set을 이용해 해결했다.
안의 값들이 항상 정렬이 되어있어야 하기 때문에
그때마다 sort를 해준다면 시간초과가 발생할 것이다.
또한 맨 앞과 맨 뒤에서 삭제를 해줄 수 있어야 하기 때문에
set을 이용하는게 적절하다고 생각했다.
전체코드
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
#include<iostream>
#include<set>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int t; cin >> t;
while (t--) {
multiset<int>arr;
int n; cin >> n;
for (int i = 0; i < n; i++) {
char a; cin >> a;
int x; cin >> x;
if (a == 'I')
arr.insert(x);
else {
if (arr.empty())
continue;
if (x == 1) {
auto iter = arr.end();
iter--;
arr.erase(iter);
}
else {
auto iter = arr.begin();
arr.erase(iter);
}
}
}
if (arr.empty())
cout << "EMPTY" << "\n";
else {
auto end = arr.end();
end--;
cout << *end << " " << *arr.begin() << "\n";
}
}
return 0;
}