[DAY78] Algorithm : Dual priority queue

이 포스트는 삽입, 최댓값 삭제, 최솟값 삭제를 모두 지원하는 이중 우선순위 큐(DPQ)를 효율적으로 구현하는 방법을 다룬다. 일반적인 std::priority_queue나 std::map 대신 std::multiset을 선택해야 하는 이유를 분석하고, 최댓값을 삭제할 때 end() 반복자를 안전하게 사용하는 C++ 문법에 대해 자세히 설명했다.

---

❓ 문제 분석

• 목표: 모든 연산(I, D 1, D -1)을 처리한 후, 큐가 비어있으면 [0, 0], 아니면 [최댓값, 최솟값]을 반환해야 한다.
• 제약 조건: operations의 길이가 최대 1,000,000이다. $\rightarrow$ 모든 연산을 $O(\log N)$ 이하로 처리하는 $O(N \log N)$ 알고리즘이 필수적이다.
• 핵심 키워드: "이중 우선순위 큐", "최댓값 삭제", "최솟값 삭제", "중복 허용".

---

💡 풀이 설계

1. 시도했던 접근 (First Attempt) & 대안 비교 ⚖️

처음에는 두 개의 표준 우선순위 큐(Max-Heap, Min-Heap)를 사용하는 방식을 고려했다.

• Lazy Deletion (지연 삭제) 방식: 힙에서 직접 삭제가 불가능하므로, 별도의 HashMap을 두어 이미 삭제된 원소를 기록해두고 힙에서 꺼낼 때 무시하는 방식이다.
  • 장점: multiset에 비해 트리 재구성 오버헤드가 적어 상수 시간 면에서 더 빠를 수 있다.
  • 단점: 삭제된 원소를 관리하는 추가 로직이 필요하여 코드가 복잡해지고, 메모리 사용량이 예측하기 어렵다.
• 결론: 본 문제에서는 시간 제한이 넉넉하고 구현의 정확성이 중요하므로, 중복을 허용하며 자동 정렬되는 std::multiset을 사용하여 코드 복잡도를 낮추는 쪽을 선택했다.

2. 최종 해결책 (Solution) ✨

std::multiset은 균형 이진 탐색 트리 기반으로 요소를 항상 정렬된 상태로 유지하며, 중복을 허용한다. 이 덕분에 최솟값(가장 앞), 최댓값(가장 뒤) 접근과 삽입/삭제가 모두 $O(\log N)$에 가능하다.

• 예상 시간 복잡도: $O(N \log N)$
• 알고리즘 흐름:
  1. std::multiset<int> dpq를 정의하고 연산 문자열을 순회한다.
  2. I (삽입): dpq.insert(data)를 수행한다.
  3. D (삭제): 큐가 비어있지 않다면,
     • data == 1: std::prev(dpq.end())를 이용해 최댓값을 삭제한다.
     • data == -1: dpq.begin()을 이용해 최솟값을 삭제한다.
  4. 연산 종료 후, *dpq.rbegin()과 *dpq.begin()을 반환한다.

---

💻 코드 구현

#include <string>
#include <vector>
#include <set>
#include <sstream>

using namespace std;

vector<int> solution(vector<string> operations) {
    // 최종 결과를 담을 벡터
    vector<int> answer; 
    
    // 이중 우선순위 큐 역할을 하는 std::multiset
    multiset<int> dpq;

    for (const string& operation : operations) {
        char command;
        int data;

        // 문자열 파싱 (예: "I 100", "D 1")
        stringstream ss(operation);
        ss >> command >> data;

        if (command == 'I') {
            // 삽입 연산: O(log N)
            dpq.insert(data);
        }
        else if (command == 'D') {
            // 삭제 연산 전, 큐가 비어있으면 무시
            if (dpq.empty()) {
                continue; 
            }
            
            if (data == 1) {
                // 최댓값 삭제: 가장 마지막 원소를 가리키는 반복자를 얻어 삭제 O(log N)
                // prev(dpq.end())는 안전하고 표준적인 방식입니다.
                dpq.erase(prev(dpq.end()));
            }
            else if (data == -1) {
                // 최솟값 삭제: 가장 첫 번째 원소를 가리키는 반복자(dpq.begin())를 얻어 삭제 O(log N)
                dpq.erase(dpq.begin());
            }
        }
    }

    // 최종 결과 반환
    if (dpq.empty()) {
        answer.push_back(0);
        answer.push_back(0);
    }
    else {
        // [최댓값 (*dpq.rbegin()), 최솟값 (*dpq.begin())] 반환
        answer.push_back(*dpq.rbegin());
        answer.push_back(*dpq.begin());
    }

    return answer;
}

🐛 시행착오 및 디버깅

• 문제점: 최댓값 삭제 시 dpq.erase(--dpq.end()) 코드가 일부 환경에서는 작동했지만, C++ 표준에 따른 안전한 사용법인지 확신이 서지 않았다.
• 원인: std::multiset의 반복자는 양방향 반복자(Bidirectional Iterator)이다. 이는 ++와 -- 연산은 지원하지만, end() - 1 같은 무작위 접근(Random Access) 연산은 표준적으로 보장되지 않는다. 일부 컴파일러는 확장 기능을 제공하지만, 이식성을 위해 표준적인 방법을 써야 한다.
• 해결: 양방향 반복자 환경에서도 안전하게 이전 위치를 가리키는 반복자를 얻을 수 있는 std::prev() 함수를 사용하여 코드를 수정했다. 코드가 더 명확해지고 이식성이 높아졌다.

✅ 오늘의 회고

항목	내용
유형	자료구조 (Data Structure)
체감 난이도	중 (자료구조 선택 및 반복자 사용이 핵심)
복잡도	시간: $O(N \log N)$, 공간: $O(N)$
새로 배운 것	1. 이중 우선순위 큐 구현 시 std::multiset이 간결한 해답이 된다. 2. multiset은 편하지만, 오버헤드가 크다면 Two Heaps + Lazy Deletion 방식을 고려해볼 수 있다. 3. std::multiset 반복자는 std::prev(iterator)를 사용해야 표준을 준수한다. 4. *dpq.rbegin()과 *dpq.begin()으로 최대/최소를 $O(1)$에 접근한다.