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

문제 설명

---

제한 사항 및 입출력 예제

---

개념

　최댓값과 최솟값 모두 처리할 수 있는 이중 우선순위 큐를 구현하는 문제다. 최소힙과 최대힙을 나눠서 처리하는 방법과, 동일한 요소를 여러 번 저장하는 multiset 자료구조를 이용하는 방법 두 가지가 있다.

---

풀이 (1)  최소힙, 최대힙

#include <algorithm>
#include <string>
#include <vector>
#include <queue>
using namespace std;

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

    for (const auto& str : operations)
    {
        string tmp = str.substr(2);

        if (str[0] == 'I')
            temp.push_back(stoi(tmp));

        else
        {
            if (tmp == "1" && !temp.empty())
                temp.erase(max_element(temp.begin(), temp.end()));

            else if(tmp == "-1" && !temp.empty())
                temp.erase(min_element(temp.begin(), temp.end()));
        }
    }

　먼저 주어진 연산은 "명령어 정수"의 형태로 이루어져 있고, 명령어의 종류는 I와 D로 나뉘어 있으므로 이를 기준으로 나눈다. 즉, 두 번째 문자부터 끝까지 잘라서 숫자 부분을 얻고, I 명령어일 경우, 해당 숫자를 임시 벡터에 추가한다. D 명령일 경우엔, 해당 숫자에 다라 최대 혹은 최소 원소를 임시 벡터에서 삭제한다.

 

    priority_queue<int, vector<int>, greater<int>> pq1;
    priority_queue<int, vector<int>, less<int>> pq2;

    for (const auto& val : temp)
    {
        pq1.push(val);
        pq2.push(val);
    }

    if (pq1.empty() && pq2.empty())
    {
        answer.push_back(0);
        answer.push_back(0);
    }

    else
    {
        answer.push_back(pq2.top());
        answer.push_back(pq1.top());
    }

    return answer;
}

　최소힙과 최대힙을 초기화하여서, 임시 벡터에 있는 값을 차례대로 힙에 넣는다. 큐가 비어있으면 문제의 조건에 맞게 [0,0]을 넣고, 아닌 경우에 [최댓값, 최솟값]을 넣은 후 벡터를 리턴하면 된다.

 

총합본

#include <algorithm>
#include <string>
#include <vector>
#include <queue>
using namespace std;

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

    for (const auto& str : operations)
    {
        string tmp = str.substr(2);

        if (str[0] == 'I')
            temp.push_back(stoi(tmp));

        else
        {
            if (tmp == "1" && !temp.empty())
                temp.erase(max_element(temp.begin(), temp.end()));

            else if(tmp == "-1" && !temp.empty())
                temp.erase(min_element(temp.begin(), temp.end()));
        }
    }

    priority_queue<int, vector<int>, greater<int>> pq1;
    priority_queue<int, vector<int>, less<int>> pq2;

    for (const auto& val : temp)
    {
        pq1.push(val);
        pq2.push(val);
    }

    if (pq1.empty() && pq2.empty())
    {
        answer.push_back(0);
        answer.push_back(0);
    }

    else
    {
        answer.push_back(pq2.top());
        answer.push_back(pq1.top());
    }

    return answer;
}

---

풀이 (2) multiset 이용

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

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

    for (const auto& str : arguments) 
    {
        string op = str.substr(0, str.find(' '));
        int val = stoi(str.substr(str.find(' ') + 1));

        if (op == "I")
            ms.insert(val);

        else if(!ms.empty())
        {
            if (val == 1)
                ms.erase(--ms.end());

            else if (val == -1)
                ms.erase(ms.begin());
        }
    }

    if (ms.empty())
        answer = { 0, 0 };

    else
        answer = { *ms.rbegin(), *ms.begin() };

    return answer;
}

　멀티셋은 자동으로 데이터를 정렬해주므로, 맨 뒤의 원소가 최댓값이 되고 맨 앞의 원소가 최솟값이 된다는 점에 착안하여 문제를 해결하였다.