[프로그래머스] 레벨3 - 이중우선순위큐

코딩테스트 연습 - 이중우선순위큐

문제 설명

최대값, 최소값을 둘 다 우선순위로 가지는 우선순위 큐를 구현하라!

연산이 주어지고 최종적으로 최대값, 최소값을 구하는 문제이다.

풀이

multiset 자료구조를 이용하면 쉽게 문제를 풀 수 있다. multiset은 중복 요소가 들어갈 수 있다. 그러므로 이중 우선순위 큐 구현에 적합하다.

코드

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    
    multiset<int, less<int>> ms;
    for (auto op : operations)
    {
        if (op == "D 1") // max erase
        {
            if (ms.empty())
                continue;
            
            ms.erase(ms.find(*(--ms.end())));
        }
        else if (op == "D -1") // min erase
        {
            if (ms.empty())
                continue;
            
            ms.erase(ms.find(*(ms.begin())));
        }
        else
        {
            int num = stoi(op.substr(2));
            ms.insert(num);
        }
    }
    
    if (ms.empty())
    {
        answer.push_back(0);
        answer.push_back(0);
    }
    else
    {
        answer.push_back(*(--ms.end()));
        answer.push_back(*(ms.begin()));
    }
    
    return answer;
}

소감

• multiset 구성및 메소드 외우기
  • multiset<int, less<int>> ms;
    • 오름차순 정렬 multiset
  • ms.erase(ms.find(value))
    • multiset에서 한 요소만 지우기

백준에 이와 똑같은 문제를 풀어봤는데 풀이가 기억나지 않아서 헤메다가 해당 백준 문제의 나의 코드를 봤다. 하지만 백준 풀이 코드보단 좀 더 간략하게 풀었다.

참조