[백준/BOJ] 백준 7662번 : 이중 우선순위 큐

www.acmicpc.net/problem/7662

7662번: 이중 우선순위 큐

multiset을 이용하여 이중 우선순위 큐를 표현했다

 

코드

#include <iostream>
#include <algorithm>
#include <set>
#include <string>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int tc;
	int k;
	string command;
	int n;
	multiset<int> q; //multiset을 이용하여 이중 우선순위 큐를 표현했다
	multiset<int>::iterator it;

	cin >> tc;

	for (int t = 0; t < tc; t++)
	{
		q.clear();

		cin >> k;

		for (int i = 0; i < k; i++)
		{
			cin >> command >> n;

			if (command == "I")
			{
				q.insert(n);
			}

			if (command == "D")
			{
				//q가 비어있을때는 무시
				if (q.empty())
					continue;

				//최댓값을 삭제한다
				if (n == 1)
				{
					it = q.end();
					it--;

					q.erase(it);
				}

				//최솟값을 삭제한다
				else if (n == -1)
				{
					it = q.begin();

					q.erase(it);
				}
			}
		}

		//q가 비어있을때
		if (q.empty())
			cout << "EMPTY" << "\n";

		else
		{
			it = q.end();
			it--;
			cout << *it << " "; //최댓값 출력

			it = q.begin();
			cout << *it; //최솟값 출력

			cout << "\n";
		}
	}


	return 0;
}