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

https://programmers.co.kr/learn/courses/30/lessons/42628?language=cpp 

코딩테스트 연습 - 이중우선순위큐

Heap

 

큐에 입력받은 숫자를 넣는 명령, 최댓값을 빼는 명령, 최솟값을 빼는 명령

들을 수행한 후에 큐에 남아있는 최댓값과 최솟값을 차례로 출력하는 문제

 

접근 방법

 

최대힙과 최소힙을 둘 다 사용해서 풀어야 하는 문제이다.

여기까지는 알겠는데 최대힙에서 top을 제거할 때 최소힙에 남아있는 수는 어떻게 하나..가 문제였다. (반대의 경우도 마찬가지)

손으로 여러번 시뮬레이션 해본 결과

최종적으로 최대힙의 top이 이미 최소힙에서 제거된 원소라면 큐에 남아있는 원소가 없음을 의미한다.는 것을 깨달았다.

따라서 실제로 큐에 원소가 하나라도 있는 상태라면 최소힙과 최대힙에서 top을 반환하면 그게 큐의 최댓값과 최솟값이 된다.

 

오답노트

 

간과했던 건

큐가 실제로는 비어있는데 힙을 비우지 않고 다음 명령을 받으면 잘못된 값을 빼게 된다.

예를 들어서 -5642, 16 이 들어있는 상태에서 두 값이 각각 다른 큐에서 빠졌다고 하자,

그 다음 123이 들어가고 최솟값을 제거하라는 명령이 입력되면?

16이 남아있는 최소힙에서는 123이 입력되었어도 top은 16이다. 근데 16은 이미 지워진 상태.

그런데도 최솟값을 제거하라는 명령에 16을 제거한다. 바른 방법이라면 123이 제거되야 함.

 

이 문제를 해결하기 위해 실제로 큐에 담아있는 원소의 개수를 카운팅한다.

그리고 큐가 비었을 때 두 개의 힙도 비워준다.

 

에드혹적으로 푼건지 잘 모르겠지만..별다른 예외 상황이 생각나지는 않는다..

프로그래머스 테케를 통과하긴 했지만 찝찝..

 

소스코드

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

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    
    priority_queue<int, vector<int>, greater<int>> minHeap;
    priority_queue<int, vector<int>, less<int>> maxHeap;
    
    int cnt = 0;
    
    for(int i = 0 ; i < operations.size() ; i++) {
        if(operations[i][0] == 'I'){
            string num = operations[i].substr(2);
            int number = stoi(num);
            maxHeap.push(number);
            minHeap.push(number);
            cnt++;
        }else {
            if(cnt == 0)
                continue;
            
            if(operations[i] == "D 1" && cnt > 0){
                maxHeap.pop();
                cnt--;
            } else if(operations[i] == "D -1" && cnt > 0) {
                minHeap.pop();
                cnt--;
            }
            
            if(cnt == 0){
                maxHeap = priority_queue<int, vector<int>, less<int>>();
                minHeap = priority_queue<int, vector<int>, greater<int>>();
            }
        }
    }
    
    if(cnt > 0){
        answer.push_back(maxHeap.top());
        answer.push_back(minHeap.top());
    } else {
        answer = {0,0};
    }
    
    
    return answer;
}