[백준 7662번 C/C++] 이중 우선순위 큐

 

[백준 7662번 C/C++] 이중 우선순위 큐

 

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

7662번: 이중 우선순위 큐

---

 

해결방안

 

우선순위 큐 priority_queue

set

 

---

 

처음 시도한 코드

 

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

int t, k;
priority_queue<int> pQ1;
priority_queue<int, vector<int>, greater<int>> pQ2;

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

	cin >> t;

	while (t--)
	{
		cin >> k;
		char input;
		int inputNum;
		int cnt = 0;
		for (int i = 0; i < k; i++) {
			cin >> input >> inputNum;

			if (input == 'I') {
				pQ1.push(inputNum);
				pQ2.push(inputNum);
				cnt++;
			}
			else if (input == 'D') {
				if (inputNum == 1) {
					if (pQ1.size() > 0)
					{
						pQ1.pop();
					}
				}
				else if (inputNum == -1) {
					if (pQ2.size() > 0)
					{
						pQ2.pop();
					}
				}
				cnt--;
			}

			if (cnt == 0)
			{
				while (!pQ1.empty()) { 
					pQ1.pop();
				}
				while (!pQ2.empty()) { 
					pQ2.pop();
				}
			}
		}

		if (pQ1.size() == 0 && pQ2.size() == 0) // 연산 후 비어있는 경우
		{
			cout << "EMPTY" << "\n";
		}
		else
		{
			cout << pQ1.top() << " " << pQ2.top() << "\n";

			while (!pQ1.empty()) { // 다음 테스트케이스 연산을 위해 비워줌
				pQ1.pop();
			}
			while (!pQ2.empty()) { // 다음 테스트케이스 연산을 위해 비워줌
				pQ2.pop();
			}
		}	
	}

	return 0;
}

---

 

정답 코드

 

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

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

	int t, k;
	cin >> t; // 테스트 케이스

	while (t--) 
	{
		cin >> k; // 연산의 개수 입력
		multiset<int> mset; // 모든 값을 저장할 multiset
		priority_queue<int> pQ1; // 최대값을 찾기 위한 우선순위 큐
		priority_queue<int, vector<int>, greater<int>> pQ2; // 최소값을 찾기 위한 우선순위 큐

		char input; 
		int inputNum; 
		for (int i = 0; i < k; i++) { 
			cin >> input >> inputNum; 

			if (input == 'I') { // 'I' 연산인 경우
				mset.insert(inputNum); // multiset에 숫자 추가
				pQ1.push(inputNum); // 최대값 우선순위 큐에 숫자 추가
				pQ2.push(inputNum); // 최소값 우선순위 큐에 숫자 추가
			}
			else { // 'D' 연산인 경우
				if (mset.empty()) continue; // multiset이 비어있는 경우 무시
                
				if (inputNum == 1) { // 'D 1' 연산인 경우
					mset.erase(mset.find(pQ1.top())); // multiset에서 최대값 삭제
					pQ1.pop(); // 최대값 우선순위 큐에서 최대값 삭제
				}
				else { // 'D -1' 연산인 경우
					mset.erase(mset.find(pQ2.top())); // multiset에서 최소값 삭제
					pQ2.pop(); // 최소값 우선순위 큐에서 최소값 삭제
				}
                
				// multiset에서 삭제된 값이 우선순위 큐에 남아있는 경우, 해당 값을 우선순위 큐에서도 삭제
				while (!pQ1.empty() && mset.find(pQ1.top()) == mset.end())
					pQ1.pop();
				while (!pQ2.empty() && mset.find(pQ2.top()) == mset.end())
					pQ2.pop();
			}
		}

		if (mset.empty()) // 모든 연산 후 multiset이 비어있는 경우
			cout << "EMPTY" << " "; // 'EMPTY' 출력
		else // multiset에 값이 남아있는 경우
			cout << *mset.rbegin() << " " << *mset.begin() << " "; // 최대값과 최소값 출력
	}

	return 0;
}

 

 

---