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

문제 링크

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

프로그래머스

 

 

코드 구현

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

using namespace std;

vector<int> solution(vector<string> operations)
{
    // 이중우선순위큐 multiset 이용 
    std::multiset<int> dq;

    for (const auto& op : operations)
    {
        // 삽입
        if (op[0] == 'I')
        {
            int num = stoi(op.substr(2));
            dq.insert(num);
        }
        // 삭제
        else
        {
            if (!dq.empty())
            {
                // multiset의 최솟값 : begin(), 최댓값 : rbegin()
                int num = stoi(op.substr(2));

                // 최댓값 삭제
                if (num > 0)
                    dq.erase(*dq.rbegin());
                // 최솟값 삭제
                else
                    dq.erase(*dq.begin());
            }
        }
    }

    // 큐가 비어있으면 [0, 0] 반환
    if (dq.empty())
        return { 0, 0 };
    // [최댓값, 최솟값] 반환
    else
    {
        int maxNum = *dq.rbegin();
        int minNum = *dq.begin();
        return { maxNum, minNum };
    }
}

 

 

해결 방법

---

• 이중우선순위큐의 특징인 최댓값과 최솟값을 빠르게 접근할 수 있는 자료구조인 std::multiset 이용
• 최솟값 : begin(), 최댓값 : rbegin()으로 접근 가능
• 입력 받은 문자열의 첫 번째 원소가 I 면 삽입 연산, D 면 삭제 연산
• 자동 정렬되기 때문에 중복되는 값이 있어도 하나의 원소만 삭제 가능