[G4] 백준 7662번 이중 우선순위 큐 C++ 멀티셋, multiset

리뷰

 

구현이 생각보다 빡세서 많이 애먹었다.. 4달 전에도 못풀었지만 4달이 지난 후에도 애를 먹은 문제 ㅠㅠ

대신 멀티셋이라는 새로운 STL을 접하게 된 계기가 되었다.

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

 

문제 풀이

1. 각 테스트 케이스마다 쿼리의 개수 k를 입력받고, 정수형 멀티셋 dic을 초기화 해준다.
2. 각 쿼리마다 I또는 D값이 입력되므로 해당 값을 문자 타입 order 변수에 입력 받는다.
3. 추가로 order 뒤에는 항상 정수 값이 입력되므로 정수형 변수 n에 값을 입력 받는다.
4. order가 I인 경우 dic에 n을 insert 해준다.
5. order가 D인 경우 dic이 비어있으면 continue, 아니라면 최대 최소에 따라 dic의 end와 begin을 erase 해준다.
6. 모든 쿼리에 대한 처리를 수행하고 dic이 비어있다면 EMPTY를 출력, 아니라면 최대 및 최소값을 출력해 준다.

 

참고 사항

최소 우선순위 큐와 최대 우선순위 큐를 따로 관리하더라도 map을 사용해 주어야 했어야 했는데, 멀티셋을 사용하니 굉장히 코드도 짧고 빠르게 풀렸다. 사실 빠른(?) 지는 모르겠다, 문제 자체가 시간제한이 6초라 널널한 편인지도 모르겠다.

 

멀티셋의 경우 중복을 허용하는 오름차순 정렬형 트리 형태이기 때문에 해당문제를 풀기에 적합했다.

최소 값을 지워줄 때는 erase의 반복자를 begin으로 설정해 줘도 되지만, 최대 값을 지워줄 때는 end에서 -1만큼 감소시켜야 한다. 왜냐하면 end 반복자의 경우 가장 뒷 부분을 가르키기 때문에 -1을 해줘야 값을 도출해 낼 수 있다.

마찬가지로 출력을 할때 *--dic.end()를 해준 이유도 그것 때문이다.

 

 

정답 코드

#include<iostream>
#include<set>

using namespace std;

int tc, k;

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

	cin >> tc;
	while (tc--) {
		cin >> k;
		multiset<int> dic;
		while (k--) {
			char order; cin >> order;
			int n; cin >> n;
			if (order == 'I') dic.insert(n);
			else {
				if (dic.empty()) continue;
				if (n == 1) dic.erase(--dic.end());
				else dic.erase(dic.begin());
			}
		}
		if (dic.empty()) cout << "EMPTY\n";
		else cout << *--dic.end()  << " " << *dic.begin() << "\n";
	}
}