프로그래머스 풀이/Lv 3
프로그래머스 - 이중우선순위 큐(C++)
홀든콜필드
2023. 3. 22. 13:41
728x90
요즘 정말 캡스톤 때문에 정신이 나갈 것 같고 학교 수업따라가기도 힘들어서 PS할 시간이없다,,,
먼저 이 문제를 보고 떠올린 키워드는 세개였다.
1. 이름부터 그렇듯 min우선순위 큐
2. max우선순위 큐
3. 덱
그리고 가장 끌렸던 것은 덱이었다.
1. 숫자를 받는다.
2. 숫자를 받다가 명령이 나오면 덱을 정렬하고 pop_front or pop_back한다.
이 방법은 명령시마다 한번씩 sort해줘야하기 때문에 좋은풀이가 아니라고 생각했다. 그러나 테스트케이스가 적어서 통과할 수 있었던 것 같다.
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<int> solution(vector<string> operations) {
vector<int> answer;
deque<int> dq;
for(auto a : operations){
if(a[0] == 'I'){
string num = a.substr(2);
int castingnum = stoi(num);
dq.push_back(castingnum);
}
else if(a[0] == 'D' && !dq.empty()){
if(a[2] == '-'){
sort(dq.begin(), dq.end());
dq.pop_front();
}else{
sort(dq.begin(), dq.end());
dq.pop_back();
}
}
}
if(dq.empty()){
answer.push_back(0);
answer.push_back(0);
}
else{
sort(dq.begin(), dq.end());
answer.push_back(dq.back());
answer.push_back(dq.front());
}
return answer;
}