https://www.acmicpc.net/problem/7662
풀이
최댓값 우선순위 큐와 최솟값 우선순위 큐를 나누어 해결하는 이중 우선순위 큐 문제이다.
이런 구조는 흔히 레드 블랙트리구조인데 , C++ 에서는 multiset이 있어 이 자체로 이중 우선순위 큐의 역할을 할 수 있다.
또한 중복데이터 삽입이 가능하며, top bottom 원소 모두 삭제가 가능하다.
Code
#include <iostream>
#include <set>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(0);
int T, K;
cin >> T;
while (T > 0)
{
multiset<int> m;
T--;
cin >> K;
for (int i = 0; i < K; i++)
{
char c;
int n;
cin >> c >> n;
if (m.empty())
{
if (c == 'I')
m.insert(n);
}
else
{
if (c == 'I')
m.insert(n);
else
{
if (n == 1)
m.erase(--m.end());
else {
m.erase(m.begin());
}
}
}
}
if (m.empty())
cout << "EMPTY" << '\n';
else
{
auto max = --m.end();
auto min = m.begin();
cout << *max << ' ' << *min << '\n';
}
}
}
'💻 OnlineJudge > Baekjoon' 카테고리의 다른 글
[백준 / BOJ] C++ 11000 강의실 배정 (0) | 2022.10.13 |
---|---|
[백준 / BOJ] C++ 2075 N번째 큰 수 (0) | 2022.10.12 |
[백준 / BOJ] C++ 1715 카드 정렬 (0) | 2022.10.06 |
[백준 / BOJ] C++ 1766 문제집 (0) | 2022.10.06 |
[백준 / BOJ] C++ 1655 가운데를 말해요 (0) | 2022.09.26 |