[baekjoon 7662] 이중 우선순위 큐 - Map, MutliMap (C++)

www.acmicpc.net/problem/7662

7662번: 이중 우선순위 큐

이중 우선순위 큐라는 문제로 값을 insert, delete 하되 최댓값과 최솟값에 접근해야 한다.

 

최대 힙, 최소 힙을 구현해서 푸는 방법도 있지만 난 STL을 연습하기 위해서 Map STL의 MutliMap을 사용했다.

 

Map의 멤버 함수에서 m.begin()과 m.rbegin()을 통해 Map의 앞과 뒤에 접근할 수 있었다.

Map은 균형 이진트리로 기본값은 오름차순이다.

즉, m.begin()을 통해 최솟값에, m.rbegin()을 통해 최댓값에 접근할 수 있다. 또한 MultiMap을 사용해서 키값을 중복되게 사용할 수 있다.

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

int T,k, N;
string s;

int main() {
	cin >> T;
	for (int t = 0; t < T; t++) {
		cin >> k;
		multimap<int, int> m;
		for (int i = 0; i < k; i++) {
			cin >> s >> N;
			if (s == "I") {
				m.insert(make_pair(N, 1));
			}
			else if (s == "D") {
				if (!m.empty()) {
					if (N == 1) {
						m.erase(m.find(m.rbegin()->first));
					}
					else {
						m.erase(m.find(m.begin()->first));
					}
				}
			}
		}
		if (m.empty())
			cout << "EMPTY" << "\n";
		else {
			cout << m.rbegin()->first << " " << m.begin()->first << "\n";
		}
	}
}

 - Insert는 받은 숫자, Delete는 m.erase(Iterator)를 넣어줘야 하기 때문에 iterator를 반환하는 find함수에 각각 최대, 최소에 해당하는 first값(key값)을 넣어주어 수행한다.

 

m.insert(k) : 원소 k 삽입, 오름차순-내림차순에 맞춰서 자동 정렬된다.

m.erase(iter) : iterator가 가리키는 원소를 제거한다.

m.find(k) : 원소 k를 가리키는 iterator를 반환한다.