문제 URL :https://www.acmicpc.net/problem/7662
7662번: 이중 우선순위 큐
입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적
www.acmicpc.net
문제 접근법 : 제목만보고 이중 우선순위 큐라길래 PQ를 사용해서 풀거라 생각했는데
map을 사용하면 너무 쉽게 해결되는 문제였습니다. map 자체의 구조를 알고있는분은
레드블랙 트리란걸 알고있고 레드블랙 트리가 무엇인지 잘 모르더라도 이진탐색트리라는것 쯤은 알고있을테니 그것의 업그레이드 판이지만 몇개의 차이점만 제외한다면 이진탐색트리와 동일하다고 보면되기때문에
map에 저장된 key값은 정렬이 되어어있기때문에 최소값은 iterator로 begin 값을 가져오면 되는것이고
최대값은 end 의 이전위치의 값을 가져오면 끝이기에 어렵게 생각할 문제는 아니었떤것같습니다.
소스코드 :
|
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
|
//By 콩순이냉장고
#include<bits/stdc++.h>
using namespace std;
int n;
map<int, int> m;
void init() {
m.clear();
}
void input() {
cin >> n;
char c;
int t;
for (int i = 0; i < n; i++) {
cin >> c >> t;
if (c == 'I') {
m[t]++; //입력받은 값의 개수를 증가
}
else {
if (m.empty())continue;
//-1이면 최소값을 아니면 최대값
int val = t == -1 ? m.begin()->first : (--m.end())->first;
m[val]--;
if (m[val] <= 0)//0이면 지우고 음수일수도 있으니 음수면 무시한다고 생각해도 됨
m.erase(val);
}
}
if (m.empty())
cout << "EMPTY" << "\n";
else
cout << (--m.end())->first << " " << m.begin()->first << "\n";
}
void solve() {
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int test;
cin >> test;
while (test--) {
init();
input();
solve();
}
}
|
cs |
궁금한점 혹은 모르는점, 논리적인 오류등 어떤질문이듯 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 9935 문자열 폭발 (0) | 2021.06.24 |
|---|---|
| 백준 1269 대칭 차집합 (0) | 2021.06.23 |
| 백준 16973 직사각형 탈출 (0) | 2021.06.23 |
| 백준 2559 수열 (0) | 2021.06.19 |
| 백준 12930 두 가중치 (0) | 2021.06.17 |