[C++] 이중우선순위큐

[문제]

코딩테스트 연습 - 이중우선순위큐 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

[문제 풀이]

"D 1"이 들어오면 최댓값을 삭제하고 "D -1"이 들어오면 최솟값을 삭제하면서 마지막에 남은 자료의 최댓값과 최솟값을 반환하는 문제이다.

최댓값의 우선순위큐와 최솟값의 우선순위큐를 만들어주고 명령어대로 "D 1"일때는 최댓값의 우선순위큐를 "D -1"일때는 최솟값의 우선순위큐를 삭제해주자.

 

또한 우선순위큐의 크기가 0이 아닐때 빼라고 한 명령어가 넣으라고 한 명령어보다 많아진 경우 내림차순, 오름차순의 우선순위큐를 최소화 해주자.

[회고]

빼라는 명령어가 넣어져있는 값보다 많아지면 삭제는 해야하는데 이를 처음에 어떻게 해야할지 헷갈려했던 문제.

난이도 자체가 어렵진 않았고 우선순위큐의 구현을 직접해야 하는 swift보다 c++이 훨씬 쉬웠던 문제.

[코드]

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

using namespace std;

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

    //작은 순서부터 넣어지는 우선순위큐와 큰 순서부터 넣어지는 우선순위 큐
    priority_queue<int,vector<int>,greater<int> > small;
    priority_queue<int> big;
    
    int cnt = 0;
    int total = 0;
    
    for(int i = 0;i<operations.size();i++){
        if(operations[i] == "D 1"){
            //최댓값 삭제.
            if(big.size() > 0){
                big.pop();
                cnt++;
            }
        }
        else if(operations[i] == "D -1"){
            //최솟값 삭제.
            if(small.size() > 0){
                small.pop();            
                cnt++;
            }
        }
        else {
            int temp = stoi(operations[i].substr(2));
            small.push(temp);
            big.push(temp);
            total++;
        }
        //만약 넣어져있는 값보다 빼는 명령어가 더 많다면 우선순위큐 초기화.
        if(cnt == total){
            big = priority_queue<int>();
            small = priority_queue<int,vector<int>,greater<int> >();
        }
    }
    
    if(cnt >= total){
        answer.push_back(0);
        answer.push_back(0);
    }
    else{
        answer.push_back(big.top());
        answer.push_back(small.top());
    }
    
    return answer;
}