[BOJ]7662 - 이중 우선순위 큐

7662

최종코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <set>
using namespace std;

multiset <int> Q;


int main() {
	int test, time;

	scanf("%d", &test);

	char c{ ' ' };
	int num{ 0 };

	for (int i = 0; i < test; i++)
	{
		scanf("%d", &time);

		for (int j = 0; j < time; j++)
		{
			scanf(" %c	%d",&c, &num);

			if (c == 'I')
			{
				Q.insert(num);
			}
			else if (c == 'D')
			{
				if (Q.empty())
					continue;

				if (num == 1)
				{
					auto index = Q.end();
					index--;
					Q.erase(index);
				}
				else
					Q.erase(Q.begin());
			}
		}
		if (Q.empty())
			printf("EMPTY\n");
		else {
			auto iter = Q.end();
			iter--;
			printf("%d %d\n", *iter, *Q.begin());
		}

		Q.clear();
	}
}

시간 초과가 나와서 찾아보니 multiset을 사용한다고 했다.

multiset은 set과 달리 중복 가능한 수를 포함할 수 있다.

원소를 넣으면 자동으로 오름차순 정렬이 되고, 트리 자료 구조로 중위 순회를 사용해서
이전 코드에서 계속 최댓값 최솟값을 찾는 것보다 빠르다.

시행착오

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

vector <int> Q;

void input(int n) {
	Q.push_back(n);
}

void maxdel() {
	int max_index = max_element(Q.begin(), Q.end()) - Q.begin();
	Q.erase(Q.begin() + max_index);
}

void mindel() {
	int min_index = min_element(Q.begin(), Q.end()) - Q.begin();
	Q.erase(Q.begin() + min_index);
}


int main() {
	int test, time;

	cin >> test;

	char c{ ' ' };
	int num{ 0 };

	for (int i = 0; i < test; i++)
	{
		cin >> time;

		for (int j = 0; j < time; j++)
		{
			cin >> c >> num;

			if (c == 'I')
			{
				input(num);
			}
			else
			{
				if (Q.empty())
					continue;

				if (num == 1)
				{
					maxdel();
				}
				else
					mindel();
			}
		}
		if (Q.empty())
			cout << "EMPTY\n";
		else {
			int max = *max_element(Q.begin(), Q.end());
			int min = *min_element(Q.begin(), Q.end());

			cout << max << " " << min << "\n";
		}

		Q.clear();
	}
}

참고자료

---

7662 솔루션
c++ set 사용법