7662. 이중 우선순위 큐

2022-04-08

백준 7662번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

풀이

아이디어

문제의 설명에 따르면 이중 우선순위 큐는 삭제가 앞과 뒤 (우선순위가 높은 것과 낮은 것) 둘 다에서 이루어 질 수 있는 우선순위 큐를 말한다. 이 큐를 구현해서, 연산을 적용하고 그 결과를 출력하면 되는 문제이다.

문제를 보자마자 그냥 … 벡터로 구현하면 되지 않을까? 하고 생각을 해 봤다. 그래서 I 명령일 경우에는 push_back으로 삽입을 해 주고, D 명령일 경우에는 sort해준 후에 옵션에 따라서 erase 함수로 원소를 지워주는 방식으로 구현을 해서 돌려봤는데 (구현이 엄청 간단함) 역시나 시간초과가 떴다. 지금 생각해보니 일단 테스트 케이스가 여러개 있는 구조이고, 삭제 시에 sort (O(NlogN) 후에 erase (O(N)) 하는 점에서 당연히 시간초과가 나지 않았을까 하는 생각이 든다. (사실 막연히 괜찮지 않을까? 했던 것은 erase의 시간 복잡도를 생각해보지 않았기 때문인데 벡터에서 erase의 시간 복잡도는 이번에 처음 알았다!

그다음으로 생각해본거는 삽입 시에 정렬 상태로 정렬이 되는 자료구조들 중에서 중복이 가능하고, 양쪽에서 삭제가 가능한 자료구조들을 생각해봤고 multiset 이 있어서 multiset을 이용해서 문제에서 요구하는 이중 우선순위 큐를 구현했다. multiset은 알고만 있었지 실제로 사용해본건 처음이었는데 그냥… 값을 중복해서 넣을 수 있다는 점만 다르고 헤더파일도, 사용 방법도 set과 동일한 것 같다. 그래서 그냥 I 일때는 insert로 삽입 해 주고 D 일 때는 옵션에 따라서 시작 혹은 끝의 원소를 삭제해 주었다. multiset의 경우에는 삽입 시에 O(logN), 그리고 삭제 시에 O(logN)으로 시간 제한을 통과할 수 있었다.

또 다른 방법으로는 priority_queue를 사용해서 최대 힙, 최소 힙을 만든 다음에 둘을 동시에 하나의 큐처럼 사용하는 방법도 있는 듯 한데 내가 보기에는 아무래도 multiset을 사용하는 방법이 더 깔끔한 것 같아보여서 다른 분의 코드만 읽어보고 직접 구현해보지는 않았다.

코드

/*
2022-4-7
7662_이중 우선순위 큐
https://www.acmicpc.net/problem/7662
*/
#include <iostream>
#include <set>

using namespace std;

multiset<int> q;
int t, k, n;
char o;

void q_delete()
{
    if (q.empty())
        return;
    if (n == 1)
        q.erase(--q.end());
    else
        q.erase(q.begin());
}

void dual_priority_queue()
{
    if (!q.empty())
        q.clear();
    cin >> k;
    for(int i = 0; i < k; i++)
    {
        cin >> o >> n;
        if (o == 'I')
            q.insert(n);
        else
            q_delete();
    }
    if (q.empty())
        cout << "EMPTY\n";
    else
        cout << *(--q.end()) << ' ' << *q.begin() << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> t;
    while (t--)
        dual_priority_queue();

    return 0;
}