[BOJ 7662] 이중 우선순위 큐

문제

이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다.

정수만 저장하는 이중 우선순위 큐 Q가 있다고 가정하자. Q에 저장된 각 정수의 값 자체를 우선순위라고 간주하자.

Q에 적용될 일련의 연산이 주어질 때 이를 처리한 후 최종적으로 Q에 저장된 데이터 중 최댓값과 최솟값을 출력하는 프로그램을 작성하라. baekjoon

코드

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>

using namespace std;

int main() {
  int tc;
  cin >> tc;

  while (tc--) {
    int k;
    cin >> k;

    vector<bool> is_in(1000000);
    // first: value, second: cmd index
    priority_queue<pair<int, int>> pq_down;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq_up;

    for (int i = 0; i < k; i++) {
      char cmd;
      int cmd_int;
      cin >> cmd >> cmd_int;

      if (cmd == 'I') {
        pq_down.push(make_pair(cmd_int, i));
        pq_up.push(make_pair(cmd_int, i));
        is_in[i] = true;
      } else {
        // D
        if (cmd_int == 1) {
          while (!pq_down.empty() && !is_in[pq_down.top().second]) pq_down.pop();
          if (!pq_down.empty()) {
            is_in[pq_down.top().second] = false;
            pq_down.pop();
          }
        } else {
          while (!pq_up.empty() && !is_in[pq_up.top().second]) pq_up.pop();
          if (!pq_up.empty()) {
            is_in[pq_up.top().second] = false;
            pq_up.pop();
          }
        }
      }
    }

    while (!pq_down.empty() && !is_in[pq_down.top().second]) pq_down.pop();
    while (!pq_up.empty() && !is_in[pq_up.top().second]) pq_up.pop();

    string result;
    if (pq_down.empty() && pq_up.empty()) result = "EMPTY";
    else result = to_string(pq_down.top().first) + " " + to_string(pq_up.top().first);
    cout << result << endl;
  }
}

풀이

우선순위 큐를 2개 준비한다. 하나는 큰 수가 우선순위가 높은, 즉 오름차순으로 정렬되는 큐와 다른 하나는 내림차순으로 정렬(이게 기본값)되는 큐다. I 명령에는 두 큐에 모두 삽입한다. D 명령시 하나의 큐에서만 삭제하게 되지만, 다른 큐에서도 이 값은 삭제되어야 한다. 하지만 즉각적으로 삭제하기엔 해당 값을 찾아서 삭제해야 하는데 비효율적이기도 하고, 기본적으로 제공되는 메소드가 없어서 불편하다. 결국 해당 값이 유효하지 않다는 표시(is_in)만 하고, 각 큐의 값에 접근할 일이 있을 때마다 이게 유효한지 안 유효한지 표식을 확인하면 된다.

원래 삽입되는 값을 통해 표시하는게 더 직관적으로 생각났었다. 같은 숫자가 여러번 나올 수 있으므로 vector<int> is_in(INT_MAX) 이런식으로 하려고 했었다. 하지만 스택이 너무 작아서 21억 크기만큼 메모리를 미리 잡아먹는게 안되나보다. new로 동적 할당해서 힙에 생성해야 하는데 벡터의 주소가 넘어오기 때문에 이용하기가 매우 불편하다. 애초에 저만한 크기가 필요하다는 것 자체가 잘못 푼게 아닌가 싶다. 그래서 여기서는 값의 유효성을 명령어의 순서로 판단한다. 순서는 중복이 생길 수 없으니 bool로 표기해도 문제가 없다.

Published 21 Sep 2019

Baekjoon