백준 Gold 4 이중 우선순위 큐

이중 우선순위 큐 (백준 Gold 4)

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

‘이중 우선순위 큐’라는 자료구조가 존재할때
최소값과 최댓값을 구하는 문제

조건

• 연산은 I와 D가 주어지며
  I는 삽입
  D는 -1,1에 따라 각각
  최솟값, 최댓값 삭제이다
  (I로 중복된 값이 들어올 수 있음)
  

• 큐가 비어있다면 D 연산은 무시
  

• 최종적으로 큐가 비어있다면 Empty를
  그렇지 않다면 최댓값, 최솟값을 출력
  

풀이 방법

처음에는 정말로 2개의 우선순위 큐를 사용하여 문제를 풀어보려 하였으나
곧바로 문제에 부딪혔다

• 각각의 큐가 중복된 값을 가지면 처리하기 까다로움
  

• 그렇다면 최소 큐 + 최대 큐 를 나누어 데이터를 관리?
  

  • 최소 큐에 작은 값, 최대 큐에 큰 값을 집어넣으면
    D와 정답 처리는 편하지만 I 를 통한 각 큐의 데이터 교환이
    힘들어짐
    
  • 그렇다고 반대로 하자니, D와 정답 처리가 까다로워 짐
    

그렇기에
생각을 바꾸어 보았다

• 정렬이 되어야 하면서, 최대 값, 최소값에 대한 접근이 비교적 가벼운 자료구조
  
• 중복된 값을 고려하는 자료구조
  

생각해보니 std::map이면 충분히 가능해보였다

• map은 자체적으로 정렬되므로 begin, rbegin을 통해 각각의 요소에 접근 가능
  
• Insert도 O(log n) 정도이고 최대 100만개 정도까지는 가능해보임
  
• Delete 역시 O(log n) 정도이고, 접근도 O(log n)
  

따라서 map으로 구현하여 문제를 풀었다

제출 코드

#include<iostream>
#include<map>
#include<string>

using namespace std;

int main()
{
	int t;
	cin >> t;

	while (t > 0)
	{
		int n;
		cin >> n;

		map<int, int> ms;

		for (int i = 0; i < n; i++)
		{
			char c;
			int v;
			cin >> c >> v;

			if (c == 'I')
			{
				ms[v]++;
			}
			else if(ms.empty() == false)
			{
				int tar = 0;
				if (v == 1)
				{
					tar = ms.rbegin()->first;
				}
				else
				{
					tar = ms.begin()->first;
				}

				ms[tar]--;
				if (ms[tar] == 0)
					ms.erase(tar);
			}
		}

		if (ms.empty())
			cout << "EMPTY" << '\n';
		else
			cout << ms.rbegin()->first << " " << ms.begin()->first << '\n';

		t--;
	}


	return 0;
}

결과

문제의 제목에 우선순위 큐 이기에
pq 관련 문제인줄 알았지만, map으로 충분히 풀 수 있는 문제였다