[프로그래머스 42628] 이중우선순위큐

AlgorithmHeap

문제

문자열 배열 operations가 주어진다. "I 숫자"는 삽입, "D 1"은 최댓값 삭제, "D -1"은 최솟값 삭제다. 모든 연산 수행 후 큐가 비어있으면 [0, 0], 아니면 [최댓값, 최솟값]을 반환한다.

핵심

최솟값과 최댓값 양쪽 삭제가 필요하므로 multiset을 쓴다. 정렬 상태를 유지하면서 양 끝 접근이 O(log N)이다.

풀이

#include <string>
#include <vector>
#include <set>
using namespace std;

vector<int> solution(vector<string> operations) {
    multiset<int> ms;

    for (const auto& op : operations) {
        if (op[0] == 'I') {
            ms.insert(stoi(op.substr(2)));
        } else if (!ms.empty()) {
            if (op == "D 1")
                ms.erase(prev(ms.end()));
            else
                ms.erase(ms.begin());
        }
    }

    if (ms.empty())
        return vector<int>{0, 0};
    return vector<int>{*ms.rbegin(), *ms.begin()};
}

메모

  • op.substr(2)는 "I 숫자" 에서 앞 두 글자("I ")를 건너뛰고 숫자 부분만 추출한다. stoi가 이를 int로 변환한다. 음수도 "I -5" → substr(2) → "-5" → stoi → -5로 정상 처리된다
  • multiset은 내부적으로 레드-블랙 트리(균형 이진 탐색 트리)로 구현된다. 원소가 항상 정렬 상태를 유지한다
  • set과 달리 중복 값을 허용한다. 이 문제에서 같은 숫자가 여러 번 삽입될 수 있으므로 multiset이어야 한다
  • 주요 API와 복잡도:
    • insert() — O(log N)
    • erase(iterator) — O(1) 상각
    • erase(값) — 해당 값 전부 삭제, O(log N + 삭제 개수)
    • begin() / rbegin() — 최솟값 / 최댓값 접근, O(1)
    • find() / count() / lower_bound() / upper_bound() — O(log N)
  • ms.erase(prev(ms.end()))로 최댓값 하나만 삭제한다. ms.erase(값)을 쓰면 해당 값 전부가 삭제되므로 반드시 iterator 버전을 써야 한다
  • prev(it)은 <iterator> 헤더의 함수로, iterator를 하나 뒤로 이동한 복사본을 반환한다. 원본 iterator는 변경하지 않는다
  • prev(it, n)처럼 두 번째 인자로 이동 칸수를 지정할 수 있다. 기본값은 1
  • 반대 방향은 next(it). prev/next 모두 --it/++it과 달리 원본을 수정하지 않아서 표현식 안에서 안전하게 쓸 수 있다
  • ms.end()는 마지막 원소 다음을 가리키는 past-the-end iterator다. prev(ms.end())가 실제 마지막 원소(최댓값)를 가리킨다
  • *ms.rbegin()도 최댓값이지만 reverse_iterator이므로 erase에 직접 넘길 수 없다. erase는 정방향 iterator만 받는다
  • priority_queue는 최솟값 또는 최댓값 한쪽만 O(1) 접근 가능하다. 양쪽이 모두 필요하면 두 개를 쓰고 동기화해야 해서 복잡하다. multiset은 양 끝 모두 접근·삭제가 가능하므로 이중 우선순위큐에 적합하다

복잡도

풀이시간공간
multisetO(N log N)O(N)