프로그래머스(힙; 이중우선순위큐) c++

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

vector<int> solution(vector<string> operations) {
    
    vector<int> v;
    for(auto& oper : operations)
    {
        if(oper[0] == 'I')
        {
            v.push_back(stoi(oper.substr(2)));
        }
        else if(oper.find("D 1") != string::npos && !v.empty())
        {
            v.erase(max_element(v.begin(), v.end()));
        }
        else if(oper.find("D -1") != string::npos && !v.empty())
        {
            v.erase(min_element(v.begin(), v.end()));
        }
    }
    
    if(v.size() == 0) return {0, 0};
    
    priority_queue<int, vector<int>, greater<int>> pq_greater = {v.begin(), v.end()};
    priority_queue<int, vector<int>, less<int>> pq_less = {v.begin(), v.end()};
    
    
    return {pq_less.top(), pq_greater.top()};
}

 

해설:

I = 삽입, D 1 = 최댓값 삭제, D -1 = 최솟값 삭제

operators의 명령어를 통해 배열을 조작하고 최댓값과 최솟값을 가져온다.

 

priority_queue -> #include <queue>

max_element -> #include <algorithm>

 

첫번쨰: int형 벡터를 선언하여 v를 선언. 범위 반복을 통해 처음 삽입에 대한 'I'를 비교 후 삽입하는 명령어, 두번째 새번째 조건은 find("D 1"), find("D -1")을 통하여 != string::npos 이고 v가 비어있지 않을경우             v.erase(max_element(v.begin(), v.end()));

            v.erase(min_element(v.begin(), v.end()));

을 실행해서 지워준다(find를 채택한 이유는 [3]으로 접근할경우에는 "I -123"같은 명령어가 존재할 수도 있기에 만약 조건 순서를 바꾸기만 해도 오류의 위치를 찾을 수 없기 때문이다).

두번쨰: v가 아무것도 없을 경우 {0, 0} 반환 priority_queue를 이용하여 greater, less을 생성 top()을 이용해 각각 {pq_less.top(), pq_greater.top()}; 으로 반환(priority_queue를 사용하지 않는 경우에는 *max_element, *min_element을 이용해 반환해도 나쁘지는 않다).