baekjoon 7662:이중 우선순위 큐

baekjoon 7662 이중 우선순위 큐

7662번 이중 우선순위 큐

접근

정방향 우선순위 큐와 역방향 우선순위 큐를 통해서 풀 수 있겠다고 생각했다.
처음에는 수가 중복될 수 있다는 발문을 보지 못하고 큐 2개 만들고 그냥 어짜피 최대, 최소만 찾으면 되고
만약 최대와 최소가 크기가 반대가 되면 EMPTY반환, 이런식으로 만들었다.

하지만 그렇게 되지 않았고(당연히 중복이 있으니까) 몇개 중복되었는지 기록할 곳을 찾았다.
처음에는 vector, 그다음엔 array, 마지막으로 map을 찾아왔다.
vector는 너무 느리고 접근 시간도 느렸다.
array는 숫자범위가 너무 커서 메모리를 너무 크게 잡아먹었다.
map은 접근 시간도 O(logn)으로 빠르고(오름차순 정리) 처음부터 key, value라는 pair과 비슷한 방식을 쓰는 것이 이 문제에 딱 맞았다.
중복을 고려하게 되면 최대와 최소보다 작다고 EMPTY, 이런식의 간단한 판정으로는 실제로 지워졌지만 우선순위 큐에 남아 있는 원소들을 제대로 찾아낼 수 없다.
결국 map이 모든 원소의 개수를 가지고 있으니까, map과 계속 동기화 시켜야한다.
언제? 특히 삭제할 때
삭제할 때 가짜 원소들을 다 삭제하고나서 진짜 원소 하나를 딱 지워야한다. 마지막에 출력할 때 도 가짜원소들을 다 삭제하고나서 진자 원소 하나를 최대, 최소로 뽑아야한다.

여담

map쓰다가 그냥 map이 모든 원소 가지고 있으니까 map만으로 만들면 끝나는거 아니야? 생각했었는데 그렇게 하니까 시간초과 떴다. 아마 map끝에서 원소 지우거나 뽑을 때마다 다 돌아야해서 그런거 같다.

코드

#include <iostream>
#include <queue>
#include <vector>
#include <map>

using namespace std;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);

  int t; cin >> t;
  while(t--){
    int k; cin >> k;
    priority_queue<int> pq;
    priority_queue<int, vector<int>, greater<int>> pq2;
    map<int, int> m;
    while(k--){
      char op; cin >> op;
      int n; cin >> n;
      if(op == 'I'){
        if(m.count(n)){
          if(m[n] == 0){
            pq.push(n);
            pq2.push(n);
          }
          m[n]++;
        }
        else{
          m[n] = 1;
          pq.push(n);
          pq2.push(n);
        }
      }
      else if (op == 'D'){
        if (n == 1){
          while(pq.empty() == false && (m[pq.top()] == 0)){
            pq.pop();
          }
          if(!pq.empty()){
            m[pq.top()]--;
            if(m[pq.top()] == 0){
              pq.pop();
            }
          }
        }
        else if (n == -1){
          while(pq2.empty() == false && (m[pq2.top()] == 0)){
            pq2.pop();
          }
          if(!pq2.empty()){
            m[pq2.top()]--;
            if(m[pq2.top()] == 0){
              pq2.pop();
            }
          }
        }
      }
    }
    while(pq.empty() == false && (m[pq.top()] == 0)){
      pq.pop();
    }
    while(pq2.empty() == false && (m[pq2.top()] == 0)){
      pq2.pop();
    }
    if (pq.empty() || pq2.empty()) {
      cout << "EMPTY\n";
      continue;
    }
    int top = pq.top(); int bottom = pq2.top();
    cout << top << " " << bottom << "\n";
  }


  return 0;
}

배운 점(+cpp 사용법)

#include <queue>
using namespace std;
int main(){
  priority_queue<int> pq; //정방향 우선순위 큐
  priority_queue<int, vector<int>, greater<int>> pq2; //역방향 우선순위 큐

  //그리고 우선순위 큐도 중복가능하다.
  pq.push(1);
  pq.push(2);
  pq.push(3);
  pq.push(3);
  pq.push(3);
  while(!pq.empty()){
    cout << pq.top() << " ";
    pq.pop();
  }
  //3 3 3 2 1
  map<int, int> m;
  m[n]++; //map m에서 key = n인 원소의 value++ or 만약 key = n인 원소 없으면 생성 후 0 + 1 = 1을 value로 입력
  m[n] = 1; //map m에서 key = n인 원소의 value = 1 or 만약 없으면 생성후 1을 value로 입력
  m.count(a); //a있으면 1, 없으면 0 반환

}