[프로그래머스] (C++) 이중우선순위큐

문제

• 링크

힌트

• 우선순위큐는 minHeap 또는 maxHeap 을 사용한다
• 이중우선순위큐는 minHeap과 maxHeap을 둘 다 사용하는 방법을 생각해보자

소스 코드 (1차 시도)

#include <iostream>
#include <queue>
#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<string> operations) {
  vector<int> answer{0, 0};
  priority_queue<int> maxHeap;
  priority_queue<int, vector<int>, greater<int>> minHeap;

  for (auto iter = operations.begin(); iter != operations.end(); iter++) {
    char action = iter->at(0);
    int num = stoi(iter->substr(2, std::string::npos));
    if (action == 'I') {
      maxHeap.push(num);
      minHeap.push(num);
    } else {
      if (num == 1) {
        if (!maxHeap.empty()) maxHeap.pop();
        if (maxHeap.empty()) minHeap = priority_queue<int, vector<int>, greater<int>>();
      } else {
        if (!minHeap.empty()) minHeap.pop();
        if (minHeap.empty()) maxHeap = priority_queue<int>();
      }
    }
  }
  if (minHeap.empty() || maxHeap.empty()) return answer;
  int max = maxHeap.top();
  int min = minHeap.top();
  bool set = false;
  while (!minHeap.empty()) {
    int pop = minHeap.top();
    minHeap.pop();
    if (pop == max) {
      set = true;
      answer[0] = max;
    }
  }
  if (!set) return answer;
  set = false;
  while (!maxHeap.empty()) {
    int pop = maxHeap.top();
    maxHeap.pop();
    if (pop == min) {
      set = true;
      answer[1] = min;
    }
  }
  if (!set) {
    answer[0] = 0;
    return answer;
  }
  return answer;
}

방법

1. operation이 넣는것이라면 input을 받아 minHeap, maxHeap 둘 다 넣는다.
2. operation이 빼는것이라면 min은 minHeap에서 max는 maxHeap에서 뺀다
3. 빈큐를 삭제하라면 무시한다
4. 결과 출력 때는 minHeap에서 min 가져오고 maxHeap에서 max 가져온다. 단, min이 maxHeap에 없으면, 또는 max가 minHeap에 없으면 0,0 반환. (다른쪽에서 이미 잦은 pop으로 이쪽 min 또는 max까지 이미 pop 한 상황)

채점 결과 (1차 시도)

합계: 83.0 / 100.0