[Programmers/C++] 이중우선순위큐

1. 문제

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

명령어	실행
I 숫자	큐에 주어진 숫자를 삽입합니다.
D 1	큐에서 최댓값을 삭제합니다.
D -1	큐에서 최솟값을 삭제합니다.

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

제한사항

• operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
• operations의 원소는 큐가 수행할 연산을 나타냅니다.
  • 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
• 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

2. 풀이

max_heap과 min_heap을 생성해서 최댓값과 최솟값을 별도로 제거한다. 입력되거나 삭제된 수의 개수는 cnt 변수로 별도로 관리하여 cnt가 0이 될 때는 max_heap과 min_heap 모두 초기화한다.

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer(2);
    priority_queue<int, vector<int>, greater<int>> min_pq;
    priority_queue<int, vector<int>, less<int>> max_pq;
    int len = operations.size(), cnt = 0;

    for (int i = 0; i < len; i++) {
        int num = stoi(operations[i].substr(2));

        if (cnt < 1) {
            while (!max_pq.empty()) max_pq.pop();
            while (!min_pq.empty()) min_pq.pop();
        }

        switch (operations[i].at(0)) {
        case 'I':
            min_pq.push(num);
            max_pq.push(num);
            cnt++;
            break;
        case 'D':
            if (cnt < 1) continue;
            if (num == 1) {
                max_pq.pop();
            }
            else {
                min_pq.pop();
            }
            cnt--;
            break;
        default:
            break;
        }
    }

    if (cnt > 1) {
        answer[0] = max_pq.top();
        answer[1] = min_pq.top();
    }

    return answer;
}

[참조]

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

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