Lv.3 / 이중우선순위큐

문제

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

프로그래머스

---

 

코드

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

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    multiset<int> ms;
    string tmp = "";

    for (int i = 0; i < operations.size(); i++) {
        char cmd = operations[i].at(0);

        if (cmd == 'D') {
            if (ms.empty()) continue;

            if (operations[i].at(2) == '1') {
                auto it = ms.end();
                it--;
                ms.erase(it);
            }
            else {
                ms.erase(ms.begin());
            }
        }
        else {
            for (int j = 2; j < operations[i].length(); j++) {
                tmp += operations[i].at(j);
            }

            ms.insert(stoi(tmp));
            tmp = "";
        }
    }

    if (ms.empty()) {
        answer.push_back(0);
        answer.push_back(0);
    }
    else {
        answer.push_back(*(ms.rbegin()));
        answer.push_back(*(ms.begin()));
    }

    return answer;
}

---

 

풀이

c++ STL 에서 제공하는 multiset 을 이용했다. multiset 은 중복이 허락되며 순서가 유지되는 set 이다.

주어진 수들에서 최소와 최대를 모두 접근해야하며 수가 중복될 수 있기에 multiset 을 이용했다.

 

만약 D 연산이라면 세번째 문자가 '-' 인지 바로 '1' 인지 확인하여 그에 맞게 최솟값 혹은 최댓값을 제거한다.

만약 I 연산이라면 문자열을 쭉 읽어 정수를 multiset 에 추가해준다.