반응형
728x170
두개의 큐를 쓰면 되지 않을까??? 생각이었지만
예외처리가 꽤나 까다로웠다.
https://www.acmicpc.net/problem/7662
여러가지 방법이 있겠지만
나는 쉬운 방법으로 풀었다.
MultiSet 자체가 무엇을 위해 만들어졌냐고 하면..?
Set이라는 것이 집합이라 중복을 허용하지 않지만..
이 친구는 key의 중복을 허용해서 유용하게 이 문제에 쓰였다.
중복이 허용되는 Set이라고 보면 된다.
자동정렬 + key,value 형태라고 보면 된다.
#맞는 풀이
#include <bits/stdc++.h>
using namespace std;
int tc;
int main(){
cin>>tc;
while(tc--){
int k;
cin >> k;
//1. ordered된 multi_set으로 중복도 포함된 set을 만들자.
multiset<int> setQ;
//2. 최댓값과 최솟값을 둘 다 이용하려면 큐를 2개 만듬.
//priority_queue<int, vector<int> less<int>> maxq;
//priority_queue<int, vector<int> grreater<int>> minq;
while(k--){
char x;
int n;
cin >> x;
cin >> n;
//I 라면 삽입
if(x == 'I'){
setQ.insert(n);
//maxq.push(n);
//minq.push(n);
}
//D 라면 삭제
else if(x == 'D' ){
if(n == 1 && !setQ.empty()){
auto it = setQ.end();
it--;
setQ.erase(it);
//if(!maxq.empty())
// maxq.pop();
}else if(n == -1 && !setQ.empty()){
setQ.erase(setQ.begin());
//if(!minq.empty())
// minq.pop();
}
}
}
if(setQ.empty()){
cout << "EMPTY";
}
else{
auto maxIt = setQ.end();
maxIt--;
cout << *(maxIt) << ' ' << *(setQ.begin());
}
cout << '\n';
}
return 0;
}
728x90
반응형
그리드형
'문제풀이(Problem Solving)' 카테고리의 다른 글
백준, BOJ, 2512번, 예산 C++ [CPP] ★★ (0) | 2022.04.10 |
---|---|
백준, BOJ, 7662번, N번째 큰 수 C++ [CPP] ★★★ (0) | 2022.03.27 |
백준, BOJ, 4358번, 생태학 C++ [CPP] ★★ (0) | 2022.03.26 |
프로그래머스, N으로 표현: C++ [CPP] ★★ (0) | 2022.03.08 |
백준, BOJ, 1525번, 퍼즐 C++ [CPP] ★★★★★ (0) | 2022.03.06 |