[프로그래머스 lv3] 이중우선순위큐 풀이

해설

최대힙과 최소힙을 따로 만들어놓자.

D -1 명령어의 경우 최소힙에서, D 1 명령어의 경우 최대힙에서 원소를 삭제하면 된다.

단, 변수 cnt에 총 원소 개수를 기록해놓고 cnt가 0이 되는 순간 최소힙과 최대힙을 깨끗하게 초기화시켜주어야 한다.

 

문제에서 남은 원소들의 [최댓값, 최솟값]을 리턴하라고 했으므로, cnt가 0이 아닐 때 {최대힙.top(), 최소힙.top()}을 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <cctype>
#include <climits>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

vector<int> solution(vector<string> operations) {

    priority_queue<int, vector<int>, greater<int>> mnpq;
    priority_queue<int, vector<int>, less<int>> mxpq;

    int cnt = 0;
    for (auto cmd : operations) {
        char c;
        int x;
        sscanf(cmd.c_str(), "%c %d", &c, &x);

        if (!cnt) {
            while (!mnpq.empty()) mnpq.pop();
            while (!mxpq.empty()) mxpq.pop();
        }

        if (c == 'I') {
            mnpq.push(x);
            mxpq.push(x);
            cnt++;
        }
        else if (x == 1 && !mxpq.empty()) {
            mxpq.pop();
            cnt--;
        }
        else if (x == -1 && !mnpq.empty()) {
            mnpq.pop();
            cnt--;
        }   
    }

    if (!cnt) return {0, 0};
    return {mxpq.top(), mnpq.top()};
}