(C++) 백준 7662 이중 우선순위 큐

문제 및 풀이

https://www.acmicpc.net/problem/7662

처음에는 무지성으로 덱으로 풀었는데 당연 시간초과 낫다 ㅎㅎㅋㅋ 어떻게 풀지 모르겠어서 다른풀이 참조함 두가지 풀이가 있었다

• map 사용
• 최대힙, 최소힙 사용

힙 사용한 풀이는 다소 번잡했고 map 사용한게 예술이었다 역시 문법을 잘 아는사람이 잘푸나보다..🥺

코드 (1) : Map

map은 key를 오름차순으로 정렬하므로, key를 입력된 숫자로 정의하고 반복자로 첫번째 원소와 마지막 원소를 접근하면 우선순위 큐의 동작을 구현할 수 있다.

• 맵의 첫번째 요소(최대값) : m.begin()->first
• 맵의 마지막 요소(최소값) : m.rbegin()->first

만약 특정 원소를 삭제해서 value가 0이되면, 더이상 큐에 존재하지 않으므로 map에서 제거하면 된다.

#include <iostream>
#include <queue>
#include <vector>
#include <map>
using namespace std;

int T,k,n;
char c;

int main() {

    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin>>T;

    while(T--){

        map<int, int> m;

        cin>>k;
        while(k--){

            cin>>c>>n;

            if(c=='D'){
                if(m.empty()) continue;

                if(n==1) {
                    if(--m[m.rbegin()->first]==0) m.erase(m.rbegin()->first);
                }
                else if(n==-1) {
                    if(--m[m.begin()->first]==0) m.erase(m.begin()->first);
                }
            }
            else { // c=='I'
                m[n]++;
            }

        }

        if(m.empty()) cout<<"EMPTY\n";
        else cout<<m.rbegin()->first<<" "<<m.begin()->first<<'\n';
    }
}

코드 (2) : Heap

maxheap과 minheap 두가지에 모두 수를 입력하고 maxheap은 front 방향, minheap은 back 방향으로 동작하는 하나의 큐로 생각해서 푼다.

다만 수가 한쪽 힙에서 pop된 경우 반대쪽 힙에서는 사용할 수 없으므로, 입력되는 수마다 인덱스를 부여해서 이 인덱스를 통해 해당 수가 pop되었는지 아니면 큐에 그대로 있는지 판단해야 한다.

D 1 (최대값 제거) 의 경우 다음과 같다.

while(!maxHeap.empty() && !isvisited[maxHeap.top().second]) 
	maxHeap.pop(); // 최대값 제거

if(maxHeap.empty()) continue;
isvisited[maxHeap.top().second]=false;
// minHeap에서 해당 값을 사용하지 않도록 false 처리 
                    

사용할 수 없는 인덱스를 계속해서 제거하고 큐가 비어있는지 확인해야 하므로 다소 복잡하다 ㅠ

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int T,k,n;
char c;
bool isvisited[1000005];

int main() {

    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin>>T;

    while(T--){

        priority_queue<pair<int, int>> maxHeap;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
        int index=0;

        cin>>k;
        while(k--){

            cin>>c>>n;

            if(c=='D'){
                if(n==1) {
                    while(!maxHeap.empty() && !isvisited[maxHeap.top().second]) maxHeap.pop();
                    if(maxHeap.empty()) continue;
                    isvisited[maxHeap.top().second]=false;
                    maxHeap.pop();
                }
                else if(n==-1) {
                    while(!minHeap.empty() && !isvisited[minHeap.top().second]) minHeap.pop();
                    if(minHeap.empty()) continue;
                    isvisited[minHeap.top().second]=false;
                    minHeap.pop();
                }
            }

            else {
                minHeap.push({n, index});
                maxHeap.push({n, index});

                isvisited[index]=true;
                index++;
            }


        }

        while (!maxHeap.empty() && !isvisited[maxHeap.top().second])
            maxHeap.pop();
        while (!minHeap.empty() && !isvisited[minHeap.top().second])
            minHeap.pop();


        if(minHeap.empty() && maxHeap.empty()) cout<<"EMPTY\n";
        else {
            cout<<maxHeap.top().first<<" "<<minHeap.top().first<<'\n';
        }
    }
}