백준 7662번 이중 우선순위 큐

🔒[문제 url]

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

🔑알고리즘

제목이 힌트인듯 priority_queue로도 해결할 수 있으나,
multiset을 이용하면 실버 하위권 문제지싶다.

• set을 이용하면 중복값을 처리할 수 없으니, 반드시 multiset을 이용할 것.

1. I 명령이 입력으로 주어지면, insert() 함수로 set에 삽입한다. 자료구조 내에서 자동 오름차순 정렬되므로, 정렬은 신경쓰지 않는다.
   다음은 7 4 9 2 5 8 11 1 3 6 10 12을 삽입했을 때의 결과이다.
   
   이처럼 가장 왼쪽에는 가장 작은 값*SET.begin()이,
   가장 오른쪽에는 가장 큰 값*--SET.end()이 온다.
   
   
2. D 명령이 주어진 경우, n == -1이라면 가장 왼쪽 값을, n == 1이라면 가장 오른쪽 값을 erase()함수를 이용해 삭제한다.
3. set이 비어있지 않다면, 가장 오른쪽 값과 왼쪽 값을 출력한다.
4. 위 과정을 테스트 케이스만큼 반복한다. set 초기화에 주의하자.

🐾부분 코드

void Insert()
{
	SET.insert(n);
}

<원소 삽입 함수>
삽입과 동시에 정렬된다. 따라서 정렬은 따로 신경쓰지 않는다.

void Delete()
{
	if (SET.empty()) return;

	if (n == -1) SET.erase(SET.begin());
	else SET.erase(--SET.end());
}

<원소 삭제 함수>
SET이 비어있는 경우 명령을 무시한다.
최소값을 삭제하는 경우 가장 왼쪽 원소를,
최대값을 삭제하는 경우 가장 오른쪽 원소를 삭제한다.

최대값을 삭제할 때, end()함수는 마지막 원소의 다음 지점을 반환하기 때문에 --SET.end()로 연산을 진행한다.

void SOLVE()
{
	while (t--)
	{
		cin >> k;
		SET.clear();
		while (k--)
		{
			cin >> command >> n;
			if (command == "I") Insert();
			else if (command == "D") Delete();
		}// while2 end

		// output
		if (SET.empty()) cout << "EMPTY\n";
		else cout << *--SET.end() << " " << *SET.begin() << '\n';

	}//while1 end

}

<testcase 반복 및 출력 함수>

SET.clear();

위 코드를 통한 테스트 케이스 사이의 SET 초기화에 주의한다.

출력시 삽입 및 삭제와 마찬가지로 end()와 begin()을 이용해 최대값과 최소값을 출력한다.

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> // cpp
#include <stdio.h> // c
#include <string>
#include <memory.h> // memset
#include <algorithm>
// 자료 구조
#include <queue>
#include <vector>
#include <stack>
#include <set>
using namespace std;
/* –2,147,483,648 ~ 2,147,483,647 */

int t, k, n;
string command;
multiset<int> SET;

void INPUT()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> t;
}

void Insert()
{
	SET.insert(n);
}

void Delete()
{
	if (SET.empty()) return;

	if (n == -1) SET.erase(SET.begin());
	else SET.erase(--SET.end());
}

void SOLVE()
{
	while (t--)
	{
		cin >> k;
		SET.clear();
		while (k--)
		{
			cin >> command >> n;
			if (command == "I") Insert();
			else if (command == "D") Delete();
		}// while2 end

		// output
		if (SET.empty()) cout << "EMPTY\n";
		else
		{

			cout << *--SET.end() << " " << *SET.begin() << '\n';
		}

	}//while1 end

}

int main()
{
	INPUT();

	SOLVE();
}

🥇문제 후기

우선순위 큐를 이용해 풀었다면, 두 개의 큐를 다루면서 큐 원소의 유효성까지 따져야하기에.. 귀찮아서 쉽게 간 문제. 큐 사용에 능숙해지고싶다면 queue로도 한 번 풀어보길 바란다. 나는 머릿속으로만 해야겠어...