프로그래머스 - 이중우선순위 큐(C++)

 요즘 정말 캡스톤 때문에 정신이 나갈 것 같고 학교 수업따라가기도 힘들어서 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;
}