[백준OJ] 7662번 이중 우선순위 큐

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

7662번: 이중 우선순위 큐

---

 

-풀이-

먼저, 최대힙,최소힙을 가지는 우선순위큐 두개를 사용해도 되는데, multiset을 이용하면 보다 더 간단하게 해결된다.

오름차순 multiset을 선언한 뒤, I면 해당 숫자를 insert해주고, D라면, 1일땐 맨 뒤의 원소를, -1일땐 맨 앞의 원소를 제거해주면 된다.

multiset은 삽입과 동시에 정렬이 되므로, 따로 정렬을 해줄 필요는 없다.

 

 

프로그래머스에 같은 문제가 있다. 맨 마지막에 이중 우선순위큐를 사용하여 푼 프로그래머스  코드를 첨부하겠다.

https://programmers.co.kr/learn/courses/30/lessons/42628

코딩테스트 연습 - 이중우선순위큐

 

 

-시간복잡도-

MultiSet:

원소의 개수를 N개라 한다면, 삽입,삭제에  O(logN) 이 걸리므로, T번 테스트케이스에 K번 쿼리를 하는것이므로, O(TKlogK)이 된다. (원소의 개수는 최대 K개이므로, K번 모두 삽입한경우)

 

 

-코드-

멀티셋을 이용한 코드

//MultiSet 을 이용한 풀이
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t;
	cin >> t;
	while (t--) {
		multiset<int> m;
		int sz = 0;
		int k, n;
		char op;
		cin >> k;
		for (int i = 0; i < k; i++) {
			cin >> op >> n;
			if (op == 'I') {
				m.insert(n);
			}
			else {
				if (m.empty()) continue;

				if (n == 1) {
					m.erase(--m.end());
				}
				else {
					m.erase(m.begin());
				}
			}
		}
		if (m.empty()) {
			cout << "EMPTY\n";
		}
		else {
			cout << *(--m.end()) << " " << *(m.begin()) << "\n";
		}
	}
	return 0;
}

2중 우선순위 큐를 이용한 코드

//2중 우선순위 큐를 이용한 풀이 [프로그래머스]
#include <string>
#include <vector>
#include<queue>
#include<iostream>
using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer(2);
    priority_queue<int> maxq,minq;
    int sz=0;
    for(int i=0;i<operations.size();i++){
        if(sz==0){
            while(!maxq.empty()) maxq.pop();
            while(!minq.empty()) minq.pop();
        }
        string op;
        string stnum;
        int num;
        op=operations[i].substr(0,1);
        stnum=operations[i].substr(2,operations[i].size()-2);
        num=stoi(stnum);
        
        if(op=="I"){
            sz++;
            maxq.push(num);
            minq.push(-num);
        }
        else{
            if(sz==0){
                continue;
            }
            else{
                if(num==1){
                    maxq.pop();
                    sz--;
                }
                else{
                    minq.pop();
                    sz--;
                }
            }
        }
    }
    if(sz){
        answer[0]=(maxq.top());
        answer[1]=(-minq.top());
    }
    
    return answer;
}