[고득점Kit][힙] 이중 우선순위 큐 ⭐⭐⭐

[힙] 이중 우선순위 큐

난이도 ⭐⭐⭐

문제

내 풀이 ⭕

별 3 개 짜리 문제들 중에선 처음으로 수월하게 빨리 풀었던 문제인 것 같다.. 어리 둥절 🤔

• 우선 순위 큐 2 개를 두었다.
  • 최대값을 우선으로 pop 하는 maxHeap 우선순위 큐
    • 최대값 삭제하는 연산 때 이 우선순위 큐에서 pop 연산
  • 최소값을 우선으로 pop 하는 minHaep 우선순위 큐
    • 최소값 삭제하는 연산 때 이 우선순위 큐에서 pop 연산
  • 삽입 연산때는 우선 순위 큐 2 개에 다 삽입
• 우선 3가지의 연산자 중 어떤 연산인지 체크하기 전에
  • ✨maxHeap.top() < minHeap.top() 이라면 큐가 비어있다고 판단하고 두 우선순위 큐를 싹 비운다.
    • 최대값 보다 최소값이 더 크다는 모순이 생기는 것이니까!
• operations 벡터를 한바퀴 전부 순회하고 나면 최종적으로
  • 두 우선순위 큐 중 하나라도 비어있다면 큐는 비어있다고 판단한다.
  • 두 우선순위 큐 둘다 비어있지 않다면 각각의 top을 pop 하여 answer 에 최대값, 최소값으로 삽입해주면 된다.

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

using namespace std;

struct cmp
{
    bool operator() (const int & a, const int & b)
    {
        return a > b;
    }
};

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    
    priority_queue<int> maxHeap;
    priority_queue<int, vector<int>, cmp> minHeap;
    
    for (auto & oper : operations)
    {
        
        if (!maxHeap.empty() && !minHeap.empty() && maxHeap.top() < minHeap.top()) // 큐가 비어있다고 판단하고 두 우선순위 큐를 싹 비운다.
        {
            while(!maxHeap.empty())
                maxHeap.pop();
            while(!minHeap.empty())
                minHeap.pop();
        } 
        
        if (oper == "D 1")  // 최대값 삭제
        {
            if (!maxHeap.empty())
                maxHeap.pop(); 
        }
        else if (oper == "D -1") // 최소값 삭제
        {
            if (!minHeap.empty())
                minHeap.pop();
        }
        else // 삽입
        {
            maxHeap.push(stoi(oper.substr(2)));
            minHeap.push(stoi(oper.substr(2)));
        }
    }
    
    /* 최종 */
    if (maxHeap.empty() || minHeap.empty())  // 비어있는 큐
    {
        answer.push_back(0);
        answer.push_back(0);
    }
    else  // 비어있지 않은 큐
    {
        answer.push_back(maxHeap.top());
        answer.push_back(minHeap.top());
    }

    return answer;
}

다른 풀이

multiset 자료구조를 사용하는 방법도 있다.

• 프로그래머스에서 multiset을 사용한 다른 분의 풀이를 봤는데 내가 푼 풀이보다 훨씬 간단하다고 느꼈다.
• multiset은 정렬되어 있고 중복 값이 가능하니까
  • 값은 multiset에 삽입하고
  • 최대값 삭제는 👉 end() 반복자에 바로 앞에 위치한 값을, 즉 최대값을 erase 해주면 된다.
  • 최소값 삭제는 👉 begin() 반복자, 가장 앞에 위치한 값을, 즉 최소값을 erase 해주면 된다.
  • 나중에 최종적으로 multiset이 비어있다면 빈 큐이고 아니라면 --end(), begin() 반복자에 위치한 값을 answer에 삽입해주면 된다.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기