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

코딩테스트 연습 - 이중우선순위큐 문제 바로가기

문제 설명

이 문제의 핵심은 최솟값과 최댓값을 실시간으로 제거할 수 있는지 입니다.
큐를 그대로 사용할 경우, C++ 에서 최대힙을 사용하기 때문에 최댓값은 바로 구할 수 있지만
최솟값은 삽입 시 -1 을 곱해야 빠르게 구할 수 있습니다.

따라서 이 문제점을 개선하고자 중복이 가능하고 실시간으로 원소들을 정렬하는
multiset 을 사용해서 문제를 해결하였습니다.

제출 코드

#include <string>
#include <vector>
#include <set>

using namespace std;

vector<int> solution(vector<string> operations) {
    multiset<int> set;
    
    for(auto oper : operations) {
        if(oper[0] == 'I') {
            int value = stoi(oper.substr(2));
            set.insert(value);
        } if(oper == "D 1" && false == set.empty()) {
            set.erase(--set.end());
        } else if(oper == "D -1" && false == set.empty()) {
            set.erase(set.begin());
        }
    }
    
    vector<int> answer(2, 0);
    if(false == set.empty()) {
        answer[0] = *(set.rbegin());
        answer[1] = *(set.begin());
    }
    return answer;
}

제출 결과