BOJ 7662 : 이중 우선순위 큐

문제링크

풀이요약

우선순위 큐

풀이상세

1. 최대힙, 최소힙 두 가지의 큐를 가지고 계산한다. 최대힙 혹은 최소힙에서 임의의 노드가 pop() 된 경우, 최대힙과 최소힙끼리 방문처리를 진행한다.

2. 방문처리의 경우, 현재 가장 앞에 있는 값의 인덱스를 체크했을 때, 최소힙 혹은 최대힙의 가장 앞의 값이라면, 그냥 바로 반환하도록 하였다.

3. 모든 작업이 끝마친 경우, 큐가 비어있다면 EMPTY 를 출력, 그렇지 않은 경우는 최대힙, 최소힙 순으로 가장 앞의 값을 반환한자.

배운점

• scanf(”%c”) 의 경우 \n 를 입력받기도 한다. 공백, regex 등 해결하는 방법이 여러가지인데 그냥 타입에 맞는 변수 잘 선언해주고 cin을 쓰면 대부분 해결된다. 왜냐면 cin은 공백과 개행을 입력받지 못하기 때문이다.

#include <iostream>
#include <queue>
#include <vector>
#define f first
#define s second
using namespace std;
int T, N;
priority_queue<pair<int, int>> maxQ;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minQ;
const int MAX = 1e6 + 4;

void updateHeap(int check[MAX]) {
    while (!maxQ.empty() && !check[maxQ.top().s]) maxQ.pop();
    while (!minQ.empty() && !check[minQ.top().s]) minQ.pop();
}

void go() {
    cin >> N;
    maxQ = priority_queue<pair<int, int>>();
    minQ = priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>();
    int check[MAX];
    char op;
    int num;
    for (int i = 0; i < N; i++) {
        cin >> op >> num;
        if (op == 'I') {
            maxQ.push({num, i});
            minQ.push({num, i});
            check[i]++;
        } else {
            if (num == 1 && !maxQ.empty()) {
                check[maxQ.top().s]--;
                maxQ.pop();
            } else if (num == -1 && !minQ.empty()) {
                check[minQ.top().s]--;
                minQ.pop();
            }
            updateHeap(check);
        }
    }
}

void output() {
    if (maxQ.empty()) cout << "EMPTY" << "\n";
    else cout << maxQ.top().f << " " << minQ.top().f << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> T;
    while (T--) {
        go();
        output();
    }
}