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

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

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

priority queue 2개로 풀어도 되지만 make_heap을 사용하면 하나로 풀 수 있다.

비교 연산자 역할을 하는 smaller와 bigger는 lambda로 대신해도 된다. 다만 자주 사용하기 때문에 비효율적이다.

extractMax 와 extractMin을 함수를 둘 다 만들지 않고 함수 포인터를 parameter로 넘겨 코드 수를 줄일 수 있었다.

bool smaller(int a, int b){ return a>b; }
bool bigger(int a, int b){ return a<b; }

int extract(vector<int>& v, bool(*compare)(int,int)){
    make_heap(v.begin(),v.end(),compare);
    pop_heap(v.begin(), v.end(),compare);
    int temp = v.back();
    v.pop_back();
    return temp;
}

vector<int> solution(vector<string> operations) {
    vector<int> v;
    for(string s:operations){
        int temp = stoi(s.substr(2));
        if(s[0]=='I'){ v.push_back(temp); } 
        else if(s[0]=='D' && !v.empty()){

            if(temp == 1 ){ extract(v,bigger); } 
            else if( temp == -1 ) { extract(v,smaller); }
        }
    }
    vector<int> answer;
    if(!v.empty()){ answer.push_back(extract(v,bigger)); } 
    else { answer.push_back(0); }
    if(!v.empty()){ answer.push_back(extract(v,smaller)); } 
    else { answer.push_back(0); }

    return answer;
}​