프로그래머스 - 이중 우선순위 큐 (C++)

 

명령어를 순서대로 처리하면 되는 문제이다.

 

특정 자료구조에 숫자를 삽입하고, 최댓값을 삭제하거나 최솟값을 삭제하는 작업을 반복한 뒤, 마지막에 남는 원소중 최댓값과 최솟값을 반환하면 된다.

 

문제 풀이

 

처음엔 문제 이름 때문에 우선순위 큐를 사용해야 하나, 덱을 사용해야 하나 고민을 했다.

하지만, 생각해보니 그냥 set을 사용하면 되는 것이었다. 정렬도 알아서 해주고, 앞이든 뒤든 중간이든 마음껏 참조하고 삭제할 수도 있기 때문이다. 다만, 동일한 숫자가 중복으로 입력될 수도 있으므로 multiset을 사용해야 한다.

(근데 해당 문제는 그냥 set을 써도 통과하긴 하더라. 테스트 케이스가 다소 부실한듯)

 

본인은 multiset 을 사용해서 명령어를 주어진 그대로 처리하였다.

 

(I 숫자)의 경우, 값을 multiset 에 삽입하였고, (D 1)의 경우 multiset 의 마지막 원소를 제거하였고, (D -1)의 경우 multiset 의 가장 앞 원소를 제거해주었다.

 

풀이 코드

std::multiset<int> Nums;

for (int i = 0; i < operations.size(); i++)
{
    std::string& CurStr = operations[i];

    if (CurStr[0] == 'I')
    {
        std::string NumberStr = CurStr.substr(2, operations.size() - 2);
        int NumberInt = std::stoi(NumberStr);

        Nums.insert(NumberInt);
    }
    else if (Nums.size() >= 1 && CurStr == "D 1")
    {
        std::multiset<int>::iterator MaxNum = Nums.end();
        MaxNum--;

        Nums.erase(MaxNum);
    }
    else if (Nums.size() >= 1 && CurStr == "D -1")
    {
        std::multiset<int>::iterator MinNum = Nums.begin();

        Nums.erase(MinNum);
    }
}

 

 

multiset을 선언하였고, 명령어를 주어진대로 처리하고 있다.

만약, 현재 문자열의 맨 앞이 I라면, 숫자 부분만 추출하여 multiset에 삽입해주었다.

 

문자열이 D 1 이라면, multiset의 가장 마지막 원소를 제거해주었다.

문자열이 D -1이라면, multiset의 가장 앞 원소를 제거해주었다.

 

만약 multiset의 size가 0이라면, 명령어를 실행하지 않고 그냥 버린다.

 

vector<int> Answer(2);

if (Nums.size() != 0)
{
    std::multiset<int>::iterator Iter = Nums.end();
    Iter--;
    Answer[0] = *Iter;

    Iter = Nums.begin();
    Answer[1] = *Iter;
}

return Answer;

 

 

모든 명령어를 실행한 뒤, set에 남아있는 원소중 가장 앞 원소와 가장 뒤의 원소를 꺼내서 답으로 출력해주었다.

 

코드 전문

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

using namespace std;

vector<int> solution(vector<string> operations)
{
    std::multiset<int> Nums;

    for (int i = 0; i < operations.size(); i++)
    {
        std::string& CurStr = operations[i];

        if (CurStr[0] == 'I')
        {
            std::string NumberStr = CurStr.substr(2, operations.size() - 2);
            int NumberInt = std::stoi(NumberStr);

            Nums.insert(NumberInt);
        }
        else if (Nums.size() >= 1 && CurStr == "D 1")
        {
            std::multiset<int>::iterator MaxNum = Nums.end();
            MaxNum--;

            Nums.erase(MaxNum);
        }
        else if (Nums.size() >= 1 && CurStr == "D -1")
        {
            std::multiset<int>::iterator MinNum = Nums.begin();

            Nums.erase(MinNum);
        }
    }

    vector<int> Answer(2);

    if (Nums.size() != 0)
    {
        std::multiset<int>::iterator Iter = Nums.end();
        Iter--;
        Answer[0] = *Iter;

        Iter = Nums.begin();
        Answer[1] = *Iter;
    }

    return Answer;
}