[C++] 프로그래머스 이중우선순위큐

https://school.programmers.co.kr/learn/courses/30/lessons/42628

프로그래머스

풀이

최소, 최대 힙을 사용한 풀이와 덱을 사용한 풀이가 있다.

최소, 최대 힙 풀이가 기억이 가물가물 해서 덱으로 풀이했다.

커멘드가 끝나고 sort 함수를 사용해서 내림차순 정렬(퀵 정렬, nlogn)만 해주면, front, back 으로 상수 시간 내에 원소에 접근할 수 있다.

#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <deque>
#include <algorithm>

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    deque<int> q;
    for (int i=0; i<operations.size(); i++){
        string cmd = operations[i].substr(0, 1);
        int num = stoi(operations[i].substr(2));
        if (cmd == "I"){
            q.push_back(num);
        }
        if (cmd == "D"){
            if (num == 1){
                if (!q.empty()) q.pop_front();
            }
            else{
                if (!q.empty()) q.pop_back();
            }
        }
        if (!q.empty()) sort(q.begin(), q.end(), greater());
    }
    if (q.empty()){
        answer.push_back(0);
        answer.push_back(0);
        return answer;
    }
    else{
        answer.push_back(q.front());
        answer.push_back(q.back());
    }
    return answer;
}