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

---

풀이

• 문제에서 요구하는 것은 최댓값과 최솟값 뿐이다.
  • 그러므로, 오름차순 priority_queue, 내림차순 priority_queue, 이렇게 두개로 관리한다.
• 삽입은 양쪽에 해주되, 최대값 삭제는 내림차순에서, 최소값 삭제는 오름차순에서 진행한다.

#include <string>
#include <vector>
#include <queue>
#include <sstream>
using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    
    priority_queue<int> pqD;
    priority_queue<int, vector<int>, greater<int> > pqU;
    int cnt = 0;
    for(int i=0; i<operations.size(); i++) {
        stringstream ss(operations[i]);
        string oper;
        string num;
        ss >> oper >> num;
        
        if(oper == "I") {
            pqD.push(stoi(num));
            pqU.push(stoi(num));
            cnt++;
        }
        else {
            if(num == "1") {
                if(!pqD.empty()) pqD.pop();
                cnt--;
            }
            else {
                if(!pqU.empty()) pqU.pop();
                cnt--;
            }
        }
    }
    
    if(cnt <= 0) {
        answer.push_back(0);
        answer.push_back(0);
    }
    else {
        answer.push_back(pqD.top());
        answer.push_back(pqU.top());
    }
    
    return answer;
}

- 최초에 이렇게 했는데, 1번 케이스가 틀렸다.
*cnt가 0이 될 때, 즉 큐가 하나라고 가정했을 때 큐가 빈 순간에 대한 처리를 해주지 않았다.

#include <string>
#include <vector>
#include <queue>
#include <sstream>
using namespace std;

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

    priority_queue<int> pqD;
    priority_queue<int, vector<int>, greater<int> > pqU;
    int cnt = 0;
    for(int i=0; i<operations.size(); i++) {
        stringstream ss(operations[i]);
        string oper;
        string num;
        ss >> oper >> num;

        if(oper == "I") {
            pqD.push(stoi(num));
            pqU.push(stoi(num));
            cnt++;
        }
        else {
            if(num == "1") {
                if(!pqD.empty()) pqD.pop();
                cnt--;
            }
            else {
                if(!pqU.empty()) pqU.pop();
                cnt--;
            }
            if(cnt <= 0) {
                while(!pqD.empty()) pqD.pop();
                while(!pqU.empty()) pqU.pop();
            }
        }
    }

    if(cnt <= 0) {
        answer.push_back(0);
        answer.push_back(0);
    }
    else {
        answer.push_back(pqD.top());
        answer.push_back(pqU.top());
    }

    return answer;
}

• 예외를 떠올리기는 정말 어렵다.