[프로그래머스] 이중우선순위큐
April 20, 2021
https://programmers.co.kr/learn/courses/30/lessons/42628
문제
문제
이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.
I: 숫자 큐에 주어진 숫자를 삽입합니다.
D 1: 큐에서 최댓값을 삭제합니다.
D -1: 큐에서 최솟값을 삭제합니다.
이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.
풀이
이중우선순위 큐를 구현하기 위해서 min-heap 을 쓰는 우선순위 큐 한 개와 max-heap 을 쓰는 우선순위 큐 한 개, 그리고 스택 한개를 사용했다. 알고리즘을 정리해보면:
- 만약 새로운 값을 넣는다면, 두 우선순위 큐에 모두 값을 넣는다.
- 최솟값을 삭제하면 min-heap 우선순위큐는 그냥 pop 을 해주고, max-heap 우선순위 큐는 모든 요소를 스택에 다 꺼냈다가 마지막으로 들어왔던 요소만 제외하고 다시 큐에 집어넣는다.
- 최댓값을 삭제하면 동일한 연산을 max-heap 우선순위큐에 대해서 진행한다.
코드
{% raw %}
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <iostream>
using namespace std;
vector<int> solution(vector<string> operations) {
vector<int> answer;
priority_queue<int, vector<int>, less<int>> positiveQ;
priority_queue<int, vector<int>, greater<int>> negativeQ;
stack<int> bucket;
for (auto op : operations) {
if (op[0] == 'I') {
int num = stoi(op.substr(2, op.size() - 1));
positiveQ.push(num);
negativeQ.push(num);
}
else if (op[0] == 'D' && isdigit(op[2])) {
if (positiveQ.empty()) continue;
positiveQ.pop();
for (int i = 0; i < positiveQ.size(); i++) {
bucket.push(negativeQ.top());
negativeQ.pop();
}
negativeQ.pop();
while (!bucket.empty()) {
negativeQ.push(bucket.top());
bucket.pop();
}
}
else if (op[0] == 'D' && !isdigit(op[2])) {
if (negativeQ.empty()) continue;
negativeQ.pop();
for (int i = 0; i < negativeQ.size(); i++) {
bucket.push(positiveQ.top());
positiveQ.pop();
}
positiveQ.pop();
while (!bucket.empty()) {
positiveQ.push(bucket.top());
bucket.pop();
}
}
}
if (positiveQ.empty()) return { 0, 0 };
else return { positiveQ.top(), negativeQ.top() };
}
{% endraw %}
