이중우선순위큐 [Lv. 3]

프로그래머스

이 문제는 주어진 문자열 명령어 리스트를 처리하여 최대값과 최소값을 동시에 관리하는 우선순위 큐를 구현하는 것입니다. 명령어는 'I x' 형식의 삽입과 'D 1' 또는 'D -1' 형식의 삭제로 구성됩니다.  

 

풀이 방법

이 문제는 min Heap, max Heap을 이용하여 푸는 문제입니다.

이 문제에서 어려움을 느낄 수 있는 부분은 둘 중 하나의 heap에서 수를 삭제 했을 때

다른 Heap에서도 해당 수를 삭제하는 것 일 것입니다.

 

저는 이 문제를 구조체를 이용해서 삭제된 수인지 체크하고

pop을 할 때 이미 삭제된 수라면 건너뛰는 방식으로 문제를 해결했습니다.

struct NODE
{
    bool isDeleted = false;
    int value;
};

else if (value == 1)
{   
    while (!maxQ.empty() && maxQ.top()->isDeleted)
        maxQ.pop();

    if (!maxQ.empty())
    {
        NODE* node = maxQ.top();
        node->isDeleted = true;
        maxQ.pop();
    }
}

 

정답 코드

- priority_queue

#include <string>
#include <vector>
#include <iostream>
#include <memory>
 
using namespace std;
 
template<typename T>
struct priority_queue
{
    priority_queue(bool b = false) : isDescOrder(b){}
    
    void push(T value)
    {
        int idx = data.size();
        data.push_back(value);
 
        while (idx > 0)
        {
            int parent = (idx - 1) / 2;
            if (!CMP(data[idx], data[parent]))
            {
                break;                
            }
            swap(data[idx], data[parent]);
            
            idx = parent;
        }
      
    }
 
        void pop()
        {
            if (data.empty())
                    return;
 
            int idx = 0;
            data[idx] = data.back();
            data.pop_back();
 
            while (idx < data.size())
            {
                int left = (idx * 2) + 1;
                int right = left + 1;
 
                if (left >= data.size())
                        break;
 
                if (right < data.size() && CMP(data[right], data[left]))
                        left = right;
 
                if (!CMP(data[left], data[idx]))
                        break;
 
                swap(data[left], data[idx]);
                idx = left;
            }
        }
    
        bool CMP(const T& a, const T& b)
        {
            if (isDescOrder)
                return *a > *b;                
            
            else
                return *a < *b;                
        }
    
        T top()
        {
            return data.empty() == true ? nullptr : data[0];
        }
 
        bool empty()
        {
            return data.empty();
        }
    
        bool isDescOrder = false;
        vector<T> data;
};

 

- solution

struct NODE
{
    bool isDeleted = false;
    int value;
 
    bool operator < (NODE other)
    {
        return value < other.value;
    }
 
    bool operator > (NODE other)
    {
        return value > other.value;
    }
 
    NODE(int v) : value(v) {};
};
 
vector<int> solution(vector<string> operations) {
    priority_queue<NODE*> minQ;
    priority_queue<NODE*> maxQ(true);
    vector<unique_ptr<NODE>> nodes;
    
    for (string& str : operations)
    {
        int value = stoi(str.substr(2));
 
        if (str[0] == 'I')
        {
            nodes.push_back(make_unique<NODE>(value));
            NODE* node = nodes.back().get();
            
            minQ.push(node);
            maxQ.push(node);
        }
        else if (value == 1)
        {   
            while (!maxQ.empty() && maxQ.top()->isDeleted)
                maxQ.pop();
            
            
            if (!maxQ.empty())
            {
                NODE* node = maxQ.top();
                node->isDeleted = true;
                maxQ.pop();
            }
            
        }
        else if (value == -1)
        {
           while (!minQ.empty() && minQ.top()->isDeleted)
                minQ.pop();
 
            if (!minQ.empty())
            {
                NODE* node = minQ.top();
                node->isDeleted = true;
                minQ.pop();
            }
        }
        
    }
 
    while (!maxQ.empty() && maxQ.top()->isDeleted == true)
        maxQ.pop();
    
    while (!minQ.empty() && minQ.top()->isDeleted == true)
        minQ.pop();
    
    int minTop = minQ.empty() ? 0 : minQ.top()->value;
    int maxTop = maxQ.empty() ? 0 : maxQ.top()->value;
    return {maxTop, minTop};
}