[Programmers] Lv3. 이중우선순위큐 | C++

🔗문제 보러가기

프로그래머스

 

🧑‍💻풀이 과정

 

(1)자동으로 오름차순으로 정렬되고, (2)중복 숫자 저장이 되며, (3)최솟값과 최댓값에 바로 접근할 수 있는 자료구조를 선정해야 합니다. 네, 바로 multiset이죠. multiset을 이용하면 쉽게 구현할 수 있습니다.

알고리즘은 다음과 같습니다.

 

1. 공백을 기준으로 입력을 분리하여, "명령어"와 "데이터" 문자열로 분리합니다.
2. "명령어"가 'I(대문자 i)'라면, multiset에 데이터를 삽입합니다.
3. "명령어"가 'D'라면, 그 뒤에 오는 데이터가 1이냐, -1이냐에 따라 분기 처리합니다.
   •  multiset이 비었다면, 무시합니다.
   • 데이터가 1이라면 최댓값을 제거해야 하므로, multiset.end() - 1을 제거합니다.
   • 데이터가 -1이라면 최솟값을 제거해야 하므로, multiset.begin()을 제거합니다.
4. 모든 명령을 처리 한 후, 답을 리턴합니다.
   • multiset이 비었다면, {0, 0}을 리턴합니다.
   • 비어 있지 않다면, { *multiset.rbegin(), *multiset.begin() }을 리턴합니다.

 

✏️소스 코드 및 결과

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

class DoublePriorityQueue
{
public:
    vector<int> GetAnswer();
    void Operate(const char instruction, int data);
    bool IsEmpty() const { return _queue.empty(); }
private:
    multiset<int> _queue;
};

void DoublePriorityQueue::Operate(const char instruction, int data)
{
    switch (instruction)
    {
    case 'I':
        _queue.emplace(data);
        break;

    case 'D':
        if (IsEmpty())
            return;

        if (data == 1)
        {
            auto maxIter = _queue.end();
            _queue.erase(--maxIter);
        }

        else if (data == -1)
        {
            auto minIter = _queue.begin();
            _queue.erase(minIter);
        }
    }
}

vector<int> DoublePriorityQueue::GetAnswer()
{
    if (IsEmpty())
        return { 0, 0 };
    return { (*_queue.rbegin()), (*_queue.begin()) };
}

vector<int> solution(vector<string> operations) {
    DoublePriorityQueue dpQueue;

    for (const auto& operation : operations)
    {
        istringstream iss(operation);
        string instruction, data;
        iss >> instruction >> data;

        dpQueue.Operate(instruction[0], stoi(data));
    }

    return dpQueue.GetAnswer();
}