[프로그래머스 코딩테스트 고득점 Kit - 힙(Heap)] 이중우선순위큐

우선순위 큐 문제

programmers.co.kr/learn/courses/30/lessons/42628

 

www.acmicpc.net/problem/7662

위 문제와 동일한 문제입니다. 테스트 케이스는 백준이 더 강력합니다.

---

[문제 풀이]

 

이중 우선순위 큐를 구현하는 문제입니다.

 

사실 자료구조에 대해 숙련이 되어 있다면 매우 간단한 문제입니다.

레드 블랙 트리 기반의 자료 구조들은 최댓값, 최솟값을 무려 $O(1)$에 불러올 수 있기 때문입니다.

즉 C++의 multiset같은 경우, 그 자체로 이중 우선순위 큐의 역할을 할 수 있습니다.

자바의 경우 TreeSet은 중복이 안되므로 TreeMap을 사용하여 중복 처리를 해주는 방식으로 해결할 수 있습니다.

 

자바는 TreeSet이면 first, last로 TreeMap이면 firstkey(entry), lastkey(entry)로 최솟값과 최댓값을 불러올 수 있습니다.

C++은 iter로 begin, end를 역참조하여 최솟값과 최댓값을 불러올 수 있습니다.

 

 

이러한 풀이도 존재하지만 직접 이중 우선순위 큐를 구현하는 방법도 설명하겠습니다.

우선순위 큐 두 개로 이중 우선순위 큐를 만들 수 있습니다.

 

단순하게 생각해보면 최대 우선순위 큐와 최소 우선순위 큐를 만든 후에

값을 넣을 때는 두 큐에 전부 넣고, 뺄 때는 최대인지 최소인지에 따라 최대 우선순위 큐 혹은 최소 우선순위 큐에서 값을 빼면 될 것 같습니다.

그러나 위의 과정대로 하면 문제가 있습니다.

 

I 1, D 1만으로 문제가 있음을 알 수 있습니다.

1을 넣고 바로 빼버리면 우선순위 큐는 비게 되지만 위의 방법으로는 최소 우선순위 큐에는 값이 남아 있어 값을 출력하게 됩니다.

 

하나의 큐에서 값을 제거하면 나머지 큐에서 값을 제거하지 못한 것이 문제입니다.

달리 말해서 두 큐를 동기화해줄 수 있으면, 최대 우선순위 큐에서 최솟값을 빼낼 수 있다면 문제가 해결됩니다.

 

최대 우선순위 큐에서는 top인 최댓값을 제외하면 전부 특정값입니다.

그것이 최솟값이라는 특징이 있더라도 특정값입니다.

그렇다면 최대, 최소 우선순위 큐에서 특정값을 제거할 수 있다면 동기화가 가능합니다.

 

특정값을 제거하고자 가장 직관적으로 생각하면, 최대 우선순위 큐에서 값을 하나 빼고 뺀 값을 저장한 뒤, 최소 우선순위 큐에서 해당 값이 나올 때까지 다른 곳에 저장한 후 값이 나온다면 그 값을 제거한 후에 저장했던 값들을 최대 우선순위 큐에 전부 넣어주는 방법이 존재합니다.

그러나 위의 특정값 제거는 $O(NlogN)$의 시간 복잡도를 갖습니다. N이 1,000,000이면 말도 안 되는 풀이입니다.

프로그래머스는 케이스가 느슨해서 모르겠지만 백준에서는 당연히 시간 초과가 납니다.

 

우선순위 큐에서 특정값 제거를 $O(logN)$에 해결하는 방법이 있습니다.

panty.run/pq-del-elem/

해당 블로그에 정리가 잘 되어 있으니 읽어보시길 권장합니다.

 

요약하자면,

 

• 최대, 최소 우선순위 큐를 만들고, 두 큐의 특정값을 lazy하게 제거할 수 있는 큐를 한 개씩 더 만듭니다.
• I입력이 들어오면 두 큐에 모두 값을 넣고,
• D입력이 들어왔을 때, 최댓값 제거라면 최대 우선순위 큐에서 값을 제거한 뒤 해당 값을 최소 우선순위 큐에서 위의 방법으로 특정값을 제거하고, 최솟값 제거라면 그 반대로 하면 됩니다.

저는 위의 방법에서 lazy하게 지운다는 방법만 착안하여 unordered_map에 특정값들을 보관하고 지워줬습니다.

풀이법을 알아도 구현하는 것에 머리를 조금 써야 하는 문제입니다.

이해하기가 어렵다면 코드를 읽어보시는 것도 좋습니다.

 

틀린 코드가 프로그래머스에서는 통과하는 경우가 있었습니다.

input: ["I 1", "I -1", "D 1", "I 2", "D -1"] / output: [2, 2] 로직이 틀린 경우 잘 걸리는 반례입니다.

---

[소스 코드] / C++

 

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

using namespace std;

template <typename T>
class dual_priority_queue {
    priority_queue<T> maxq;
    priority_queue<T, vector<T>, greater<T>> minq;
    unordered_map<T, int> maxdel, mindel;

public:
    dual_priority_queue() {}

    void push(T data) {
        maxq.push(data);
        minq.push(data);
    }

    void popMax() {
        T data = maxq.top();
        maxq.pop();

        if (!mindel.insert(make_pair(data, 1)).second) {
            ++mindel[data];
        }

        synchronize();
    }

    void popMin() {
        T data = minq.top();
        minq.pop();

        if (!maxdel.insert(make_pair(data, 1)).second) {
            ++maxdel[data];
        }

        synchronize();
    }

    bool empty() {
        return maxq.empty() || minq.empty();
    }

    T topMax() {
        return maxq.top();
    }

    T topMin() {
        return minq.top();
    }

    void synchronize() {
        while (!minq.empty()) {
            T cur = minq.top();
            if (mindel.find(cur) == mindel.end()) break;
            if (--mindel[cur] == 0) mindel.erase(cur);
            minq.pop();
        }

        while (!maxq.empty()) {
            T cur = maxq.top();
            if (maxdel.find(cur) == maxdel.end()) break;
            if (--maxdel[cur] == 0) maxdel.erase(cur);
            maxq.pop();
        }
    }
};


vector<int> solution(vector<string> operations) {
    vector<int> answer = {0, 0};
    dual_priority_queue<int> dpq;

    for (string s : operations) {
        stringstream ss(s);
        string command;
        int number;
        ss >> command >> number;

        if (command == "I") {
            dpq.push(number);
        }
        else {
            if (dpq.empty()) continue;

            if (number == 1) dpq.popMax();
            else dpq.popMin();
        }
    }

    if (!dpq.empty()) {
        answer[0] = dpq.topMax();
        answer[1] = dpq.topMin();
    }

    return answer;
}

 

---

[참고]

 

• chbuljumeok1997.tistory.com/42
• psychoria.tistory.com/709
• min-zero.tistory.com/entry/C-STL-1-2-%ED%85%9C%ED%94%8C%EB%A6%BF-%ED%81%B4%EB%9E%98%EC%8A%A4-%ED%85%9C%ED%94%8C%EB%A6%BFclass-template
• blockdmask.tistory.com/43
• panty.run/pq-del-elem/