프로그래머스lv3 _ 이중우선순위큐

2020-09-04 · 배운 것 · 3분 읽기

programmers.co.kr/learn/courses/30/lessons/42628

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

풀이방법

문제는 최대힙으로 풀라고 권장하지만 multiset으로 푸는편이 더 깔끔하고 쉬워서 그렇게 풀었다.
참고로 multiset은 자동 정렬이 된다.

코드

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

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    
    multiset<int> container;

    for (auto ele : operations)
    {
        if (ele[0] == 'I')
        {
            string strNum = ele.substr(2, ele.size() - 2);
            int num = stoi(strNum);
            container.insert(num);
        }
        else if(ele[0] == 'D')
        {
            //비었을경우 무시
            if (container.empty())
                continue;

            if (ele[2] == '1')
                container.erase(--end(container));
            else
                container.erase(begin(container));
        }
    }

    if (container.empty())
        answer = { 0, 0 };
    else
        answer = { *(--end(container)), *begin(container)};

    cout << answer[0] << " " << answer[1] << endl;

    return answer;
}

멀티셋을 이용하니 간단했다.