[Programmers 코딩 연습] 이중우선순위큐 [Level 3]

문제(출처)-프로그래머스

자료구조

• 이중우선순위큐
  (최솟값, 최댓값 둘 다 찾을 수 있는 우선순위큐)

설명

문제를 푸는 과정은 다음과 같다.

1. for each operation in operations
2.     determin operation type (insert or delete)
3.     if operation is "insert"
4.         insert number into double priority queue
5.     else if operation is "delete min"
6.         delete min value from double priority queue
7.     else
8.         delete max value from double priority queue

2번 라인을 위해 parse_operation() 함수를 만들어서 insert는 0, delete min은 -1, delete max는 1을 반환하도록 했다.

4번, 5번, 6번 라인을 위해 각각 insert_dpq(), delete_min(), delete_max() 함수를 만들었다.

이중우선순위큐를 직접 구현하는 대신 삽입 삭제 시 정렬이 되는 set 자료구조를 이용하였다.

소스코드

cpp

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

using namespace std;

int parse_operation(string &oper);
void delete_min(set<int> &dpq);
void delete_max(set<int> &dpq);
void insert_dpq(set<int> &dpq, int num);

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    set<int> dpq; //set은 안에서 자동으로 정렬이 이루어진다. -> 우선순위 적용과 같은 효과
    
    for (string &oper : operations) {
        switch(parse_operation(oper)) {
            case 0:
                insert_dpq(dpq, stoi(oper.substr(2)));
                break;
            case 1:
                delete_max(dpq);
                break;
            case -1:
                delete_min(dpq);
                break;
        }
    }
    
    if (dpq.empty())
        answer = {0,0};
    else {
        set<int>::iterator it = dpq.end();
        answer = {*(it-1), *dpq.begin()};
    }
    
    return answer;
}

int parse_operation(string &oper) {
    switch (oper[0]) {
        case 'I':
            return 0;
        case 'D':
            if (oper[2] == '-')
                return -1;
            return 1;
    }
    return -2;
}
void delete_min(set<int> &dpq) {
    if (!dpq.empty())
        dpq.erase(dpq.begin());
}
void delete_max(set<int> &dpq) {
    if (!dpq.empty()) {
        set<int>::iterator it = dpq.end();
        dpq.erase(--it);
    }
}
void insert_dpq(set<int> &dpq, int num) {
    dpq.insert(num);
}

참고

1. set의 메서드
   • .insert(element) // insert element into set
   • .erase(iterator pos) // erase an element at pos
   • .empty() // return true/false
2. set은 내부에서 자동으로 정렬된다.
   • 정렬을 사용자 정의로 하고 싶다면, set<key, decltype(compare function)> dpq;와 같이 선언해주면 된다.
3. set은 iterator를 이용하여 탐색해야 한다.
4. key를 찾을 때는 .find(key)를 쓰면 된다.
   • key가 없으면 .end()와 같다.