[알고리즘 문제] 자료구조 - 프로그래머스 이중 우선순위 큐(level 3)

문제 이해

이중 우선순위 큐는 다음 세 연산을 처리합니다.

I n   : n을 삽입한다.
D 1   : 최댓값 하나를 삭제한다.
D -1  : 최솟값 하나를 삭제한다.

큐가 비어 있을 때의 삭제 명령은 무시합니다. 모든 명령을 처리한 뒤 비어 있으면 [0, 0], 값이 남아 있으면 [최댓값, 최솟값]을 반환합니다. 같은 최댓값이나 최솟값이 여러 개 있어도 삭제하는 값은 하나뿐입니다.

왜 multiset을 선택했는가

일반적인 최소 힙은 최솟값에는 빠르게 접근하지만 최댓값 삭제에는 적합하지 않습니다. 최대 힙도 반대 문제가 있습니다. 두 힙과 지연 삭제를 조합할 수도 있지만, 이 문제에서는 정렬 상태를 유지하는 multiset이 더 간결합니다.

• 같은 값을 여러 번 저장할 수 있다.
• 원소가 자동으로 오름차순 정렬된다.
• begin()으로 최솟값, 마지막 원소로 최댓값에 접근할 수 있다.
• 삽입과 반복자를 이용한 삭제가 모두 O(log N)이다.

set은 중복 값을 저장하지 못하므로 사용할 수 없습니다. 예를 들어 5를 두 번 삽입한 뒤 한 번 삭제해도 5 하나가 남아야 합니다.

명령어를 문자와 값으로 나누기

operations의 각 문자열은 명령과 정수가 공백으로 구분됩니다. stringstream을 사용하면 음수도 별도 처리 없이 정수로 읽을 수 있습니다.

for (const string& operation : operations) {
    stringstream ss(operation);

    char command;
    int value;
    ss >> command >> value;

    if (command == 'I') {
        values.insert(value);
    }
}

D -1도 command == 'D', value == -1로 자연스럽게 분리됩니다.

양 끝 원소를 하나만 삭제하기

정렬된 multiset에서 begin()은 첫 원소, end()는 마지막 원소 다음 위치를 가리킵니다.

if (command == 'D' && !values.empty()) {
    if (value == 1) {
        values.erase(prev(values.end())); // 최댓값 하나
    } else {
        values.erase(values.begin());     // 최솟값 하나
    }
}

여기서는 반드시 반복자를 erase에 전달해야 합니다. values.erase(value)처럼 값을 전달하면 그 값과 같은 원소를 모두 지우기 때문입니다. 반복자를 전달하면 해당 위치의 원소 하나만 삭제되어 문제 조건과 일치합니다.

또한 빈 컨테이너에서 begin()이나 prev(end())를 삭제 대상으로 사용하면 안 되므로 먼저 empty()를 검사합니다.

일반 반복자와 역방향 반복자의 차이

prev(values.end())와 values.rbegin()은 모두 마지막 원소를 바라보지만 반복자 타입과 이동 방향이 다릅니다.

values.begin()           // 최솟값을 가리키는 iterator
prev(values.end())       // 최댓값을 가리키는 iterator
values.rbegin()          // 최댓값을 가리키는 reverse_iterator

multiset::erase에는 일반 반복자를 전달하는 편이 가장 단순하므로 삭제할 때는 prev(values.end())를 사용합니다. 반면 조회할 때는 역참조만 하면 되므로 *values.rbegin()이 읽기 쉽습니다.

rbegin()에서 일반 반복자로 변환해야 한다면 base()가 가리키는 위치에 주의해야 합니다.

auto reverseIt = values.rbegin();
values.erase(prev(reverseIt.base()));

역방향 반복자의 base()는 같은 원소가 아니라 그 원소의 다음 위치를 가리킵니다. 그래서 prev()로 한 칸 되돌려야 실제 최댓값의 일반 반복자가 됩니다.

두 번째 예제로 연산 흐름 확인하기

I -45  → {-45}
I 653  → {-45, 653}
D 1    → {-45}
I -642 → {-642, -45}
I 45   → {-642, -45, 45}
I 97   → {-642, -45, 45, 97}
D 1    → {-642, -45, 45}
D -1   → {-45, 45}
I 333  → {-45, 45, 333}

모든 연산이 끝난 뒤 최댓값은 333, 최솟값은 -45이므로 [333, -45]를 반환합니다.

최종 코드

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

using namespace std;

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

    for (const string& operation : operations) {
        stringstream ss(operation);
        char command;
        int value;
        ss >> command >> value;

        if (command == 'I') {
            values.insert(value);
            continue;
        }

        if (command == 'D' && !values.empty()) {
            if (value == 1) {
                values.erase(prev(values.end()));
            } else {
                values.erase(values.begin());
            }
        }
    }

    if (values.empty()) {
        return {0, 0};
    }

    return {*values.rbegin(), *values.begin()};
}

복잡도와 체크포인트

• 시간복잡도는 O(M log M)
• 명령 수를 M이라 하면 각 삽입과 삭제가 최대 O(log M)입니다. 문자열 파싱 비용을 포함해도 입력 길이에 비례하는 범위 안입니다.
• 공간복잡도는 O(M)
• 삭제되지 않은 값이 최악의 경우 명령 수만큼 multiset에 남습니다.
• 빈 큐의 삭제는 무시한다
• 삭제 전에 empty()를 확인해야 유효하지 않은 반복자를 만들지 않습니다.
• 중복 원소는 한 개만 삭제한다
• 값이 아니라 반복자를 전달하는 erase(iterator)를 사용합니다.
• 반환 순서는 최댓값, 최솟값이다
• 문제의 반환 형식은 {*values.rbegin(), *values.begin()} 순서입니다.

정리

• 최솟값과 최댓값을 모두 자주 삭제해야 하므로 정렬 상태를 유지하는 multiset을 사용한다.
• begin()은 최솟값, prev(end())는 최댓값의 일반 반복자다.
• 반복자로 삭제하면 중복된 최솟값이나 최댓값 중 하나만 제거할 수 있다.
• rbegin().base()는 역방향 반복자가 바라보는 원소의 다음 위치라는 점에 주의한다.
• 모든 명령을 O(M log M)에 처리할 수 있다.

처음에는 직접 힙이나 연결 구조를 구현하는 방식을 떠올렸지만, 표준 컨테이너가 보장하는 정렬과 연산 복잡도를 문제 조건에 맞춰 선택하는 것이 더 중요했습니다. 자료구조의 성질뿐 아니라 erase 오버로드와 반복자의 방향까지 이해해야 문제의 “중복 값 하나만 삭제” 조건을 정확히 구현할 수 있었습니다.