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

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

프로그래머스

 

 

해결 방법

멀티셋은 자동으로 정렬이 되며, 중복값을 허용하는 자료구조이다. 멀티셋의 맨 앞 요소는 가장 작은 값이, 맨 뒤 요소는 가장 큰 값이들어온다. 

 

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

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

    multiset<int> s;
    for(int i = 0; i<operations.size(); i++){
        istringstream iss(operations[i]);
        string command = ""; string numstr ="";
        iss>>command >> numstr;
    
        if(command == "I"){
            s.insert(stoi(numstr));
        }else if(command == "D"){
            if(s.size() == 0) continue;
            if(numstr == "1") {
             auto it = s.end();
                --it;
                s.erase(it);
            }
            else s.erase(s.begin());
        }
    }
    
    if(s.size() ==0) return vector<int>(2,0);;
    
    answer.push_back(*s.rbegin());
    answer.push_back(*s.begin());

    return answer;
}

 

 

 

다른 풀이

처음엔 최대 우선순위 큐 , 최소 우선순위 큐 2개를  이용하여 풀려고 했었다. 실패했었는데, 여기 그 방법으로 풀어서 성공한 다른 사람의 해결방법이 있다.

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

using namespace std;

priority_queue<int,vector<int>,greater<int>> min_heap;
priority_queue<int> max_heap;

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

    for(int i=0;i<arguments.size();i++)
    {
        string a = arguments[i];
        char o = a[0];
        int n = atoi(a.substr(2).c_str());

        if(o == 'I')
        {
            min_heap.push(n);
            max_heap.push(n);
        }
        else if(o == 'D' && n == 1)
        {
            if(max_heap.empty()) continue;
            if(max_heap.top() == min_heap.top()) min_heap.pop();
            max_heap.pop();
        }
        else if (o == 'D' && n == -1)
        {
            if(min_heap.empty()) continue;
            if(max_heap.top() == min_heap.top()) max_heap.pop();
            min_heap.pop();
        }

        if(max_heap.top() < min_heap.top())
        {
            while(!min_heap.empty()) min_heap.pop();
            while(!max_heap.empty()) max_heap.pop();
        }
    }

    if(min_heap.empty()) 
    {
        answer.push_back(0);
        answer.push_back(0);
    }
    else
    {
        answer.push_back(max_heap.top());
        answer.push_back(min_heap.top());
    }

    return answer;
}