프로그래머스 (이중우선순위큐, 힙(Heap)) C++

 

 

priority_queue<int, vector<int>, greater<int>> => Min Heap
priority_queue<int, vector<int>, less<int>> => Max heap

 

우선순위 큐는 최댓값과 최솟값을 가장 효율적으로 확인할 수 있는 방법이므로 해당 STL을 사용한다면 손쉽게 문제를 해결할 수 있다. 여기서 중요한 것은 두 개의 Heap으로 하나의 상황을 처리하다보니까 heap의 크기를 동일하게 카운트 해줄 수 있는 변수가 필요했다는 점이다. 만약 pop을 했는데 크기가 0이 된 경우 두 개의 Heap을 모두 초기화해줄 필요가 있었다. (제일 중요한 점)

 

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

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    int heap_size = 0;
    
    // Max 힙과 Min 힙을 선언한다.
    priority_queue<int, vector<int>, greater<int>> min_heap;
    priority_queue<int, vector<int>, less<int>> max_heap;
    
    for(int i = 0 ; i < operations.size() ; i++) {
        
        // 공백을 포함한 문자를 쉽게 구분하기 위한 빌드업
        string str[3];
        string token;
        
        // stringstream으로 token을 만들어 정리해놓는다.
        stringstream ss(operations[i]);
        int count = 0;
        
        // str 벡터 안에 원하는 값을 담는다.
        while(ss >> token) 
            str[count++] = token;
        
        // str[0] 에는 문자 str[1]에는 추가할 숫자가 들어간다.
        int digit = stoi(str[1]);
        
        // I 인 경우 max와 min Heap에 값을 넣어준다.
        if(str[0] == "I") {
            heap_size++;
            max_heap.push(digit);
            min_heap.push(digit);
        }
        
        // D인 경우 pop을 시행한다.
        else if(str[0] == "D" && heap_size != 0) {
            // pop의 경우 heap의 전체적인 사이즈를 하나씩 줄여준다.
            heap_size--;
            
            // 만약 heap을 줄였는데 사이즈가 0이 되었으면 다시 초기화를 해야한다.
            if(heap_size == 0) {
                min_heap = priority_queue<int, vector<int>, greater<int>>();
                max_heap = priority_queue<int, vector<int>, less<int>>();
            }
            
            // digit이 1인 경우 최대값을 제거하므로 max_heap의 pop을 한다.
            if(digit == 1) {                
                if(!max_heap.empty()) {
                    max_heap.pop();
                }
            }
            
            // digit이 -1인 경우 최솟값을 제거하므로 min_heap의 pop을 한다.
            else if(digit == -1) {
                if(!min_heap.empty())
                    min_heap.pop();
            }
        }
    }
    
    // 힙의 크기가 0인 경우 [0, 0] 을 넣어준다.
    if(heap_size == 0) {
        answer.push_back(0);
        answer.push_back(0);
    }
    
    // 아닌 경우 최댓값과 최솟값의 top을 추가한다.
    else {
        answer.push_back(max_heap.top());
        answer.push_back(min_heap.top());
    }
    
    return answer;
}