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

---

🔗 문제 링크

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

프로그래머스

---

반응형

728x90

👩‍💻 코드

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

using namespace std;

vector<int> solution(vector<string> operations) {
    multiset<int> ms;
    
    for(auto &operation : operations){
        if(operation[0] == 'I'){
            int number = stoi(operation.substr(2));
            ms.insert(number);
        }else if(!ms.empty()){
            if (operation == "D 1") {
                auto max_it = prev(ms.end());
                ms.erase(max_it);
            } 
            else if (operation == "D -1") {
                ms.erase(ms.begin());
            }
        }
    }
    
    if (ms.empty()) {
        return {0, 0};
    }
    
    return {*prev(ms.end()), *ms.begin()};
}

---

📝 풀이

multiset 컨테이너를 사용하면 간단하게 문제를 풀 수 있습니다.

multiset은 요소를 자동으로 정렬하고 중복을 허용하여 최댓값과 최솟값에 O(1) 시간 복잡도로 접근 할 수 있기 때문입니다.