BaekJoon 7662번: 이중 우선순위 큐(C++)

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

7662번: 이중 우선순위 큐

풀이법

1) 제한시간이 6초이기에 넉넉하다고 생각하여, for문이나 정렬을 하게 되면 무조건 시간 초과가 나는 문제이다.

2) 문제를 해결함에 있어 중복이 가능하고 RBTree의 형태를 가진 set 자료형을 사용하였다.

3) 값을 insert하게 되면 오름차순으로 알아서 정렬이 되기에, set 자료형을 사용한다면 쉽게 문제를 풀 수 있다.

 

set 자료형 사용 시 주의 사항

auto it=set.end() 자료형을 담게되면, 마지막 원소 다음을 가르키는 iterator를 반환한다

그렇기에 꼭 it--을 하여 마지막 원소를 가르킬 수 있게끔하는 것이 중요하다.

직접적으로 auto it에 담긴 값을 뽑기 위해서는 *it을 사용하면 쉽게 뽑아낼 수 있다.

마찬가지로 *s.begin()을 사용한다면 바로 set 자료형 안에 담긴 값을 뽑아낼 수 있다.

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

int t;
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> t;
	for (int k = 0; k < t; k++)
	{
		int n;
		cin >> n;
		multiset<int> s;
		for (int i = 0; i < n; i++)
		{
			char c;
			int a;
			cin >> c >> a;
			if (c == 'I')
				s.insert(a);
			else
			{
				if (s.empty())
					continue;
				if (a == 1)
				{
					auto it = s.end(); // 마지막 원소 다음을 가르키는 iterator 리턴
					it--;
					s.erase(it);
				}
				else if (a == -1)
				{
					auto it = s.begin();
					s.erase(it);
				}
			}
		}
		if (s.empty())
			cout << "EMPTY"<<"\n";
		else
		{
			auto it = s.end();
			it--;
			cout << *it << " " << *s.begin() << "\n";
		}
	}

}