C++ / 백준 / 7662 / 이중 우선순위 큐

문제

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

7662번: 이중 우선순위 큐

문제풀이

map을 이용해서 풀었다.

I 숫자는 입력이므로 cin >> oper >> n을 통해 I와 값을 입력받고 map인 m을 선언하였으므로 m[n]의 값을 1 증가시킨다.

연산이 D 1일 경우 최댓값을 삭제해야 한다.

그래서 iterator인 iter을 선언하고 m의 end부분으로 간 뒤 한 칸 앞으로 이동(--m.end())한다.

동일한 값을 입력받을 수 있으므로 최댓값이 몇 개 입력됐는지 확인을 한다.

여러 개가 입력되었을 경우는 iter을 통해 m[n]값인 iter->second를 1 줄인다.

해당 값이 한 번만 입력되었을 경우는 erase를 통해 지운다.

while문이 종료되면 m이 비었을 경우는 EMPTY를, 그 외의 경우는 최댓값, 최솟값을 출력한다.

 

코드

#include <iostream>
#include <map>
using namespace std;

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

	int T(0), k(0), n(0);
	char oper(' ');
	cin >> T;

	while (T--) {
		cin >> k;
		map<int, int>m;
		map<int, int>::iterator iter;
		while (k--) {
			cin >> oper >> n;
			if (oper == 'I') {
				m[n]++;
			}
			else {
				if (!m.empty()) {
					if (n == 1) {
						iter = --m.end();						
						if (iter->second == 1)
							m.erase(iter);
						else iter->second--;
					}
					else {
						iter = m.begin();
						if (iter->second == 1)
							m.erase(iter);
						else iter->second--;
					}
				}
			}
		}

		if (m.empty()) cout << "EMPTY\n";
		else {
			cout << (--m.end())->first << " ";
			cout << m.begin()->first << '\n';
		}
	}
}