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

 

이 문제를 처음 보고, 자동 정렬되는 multiset을 이용하면 되지 않을까 생각했다가

최대 최소를 동시에 다뤄주지 못하진 않을까 생각하여 다르게 구현했지만, 이것이 가능했었다.

 

게다가 이 문제는 내가 약 1년전에 multiset을 처음 접하여 풀었던 똑같은 문제다(https://hevton.tistory.com/427)

 

 

우선 내가 multiset없이 vector로 푼 방식은 이러하다.

#include <string>
#include <vector>
#include <deque>
#include <sstream>
#include <algorithm>

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    
    deque<int> dq;
    
    string command;
    int value;
    
    for(auto oper : operations) {
        
        
        stringstream ss(oper);
        ss >> command >> value;
        
        
        if(command == "I") {
            dq.push_back(value);
        } else if(command == "D" && value == 1 && dq.size() > 0) {
            dq.pop_back();
        } else if(command == "D" && value == -1 && dq.size() > 0) {
            dq.pop_front();
        }
        
        sort(dq.begin(), dq.end());

        
    }
    
    if(dq.size() == 0)
        answer = {0, 0};
    else
        answer = {dq.back(), dq.front()};
    
    return answer;
}

이렇게 매번 정렬해 주는 방식으로 풀었다.

 

 

이제 multiset에 대해서 알아보자.

#include <iostream>
#include <set>
using namespace std;

int main() {
    
    
    multiset<int> ms;
    
    ms.insert(5);
    ms.insert(1);
    ms.insert(4);
    ms.insert(3);
    ms.insert(2);
    
    
    for(auto i = ms.begin(); i != ms.end(); i++) {
        
        cout << *i << " ";
        
    }
    
    
}

/*
OUTPUT : 1 2 3 4 5
*/

이렇게, iterator를 통해 traversal이 가능하다.

 

하지만 priority_queue로 구현하는 Heap 같은 경우에는, pop 작업 없이는 rebalanace가 안되므로 순회가 불가능하다.

#include <iostream>
#include <queue>
using namespace std;

int main() {
    
    
    priority_queue<int, vector<int>, greater<int>> pq;
    
    pq.push(3);
    pq.push(4);
    pq.push(1);
    pq.push(5);
    pq.push(2);
    

    
}

 

아무튼 multiset을 이용하면 이 문제를 이렇게 풀 수 있다.

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

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    
    multiset<int> ms;
    
    string cmd;
    int value;
    
    for(auto oper : operations) {
        
        stringstream ss(oper);
        ss >> cmd >> value;
        
        if(cmd == "I") {
            ms.insert(value);
        } else if(cmd == "D" && ms.size() > 0) {
            
            if(value == 1) {
                ms.erase(--ms.end());
            } else {
                ms.erase(ms.begin());
            }
            
        }
        
    }
    
    if(ms.size() == 0)
        answer = {0, 0};
    else
        answer = {*(--ms.end()), *ms.begin()};
    
    return answer;
}

주의할 점은, ms.end()는 마지막 인자 그 뒤를 가리키기 때문에, 그 이전을 가리켜야한다.

 

 

---

started at 19:34

ended at 20:05