[백준] 7662번: 이중 우선순위 큐 C++로 풀어보기

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

7662번: 이중 우선순위 큐

 

7662번 설명

생각

동일한 정수가 삽입될 수 있다. -> 중복이 허용된다.

최댓값과 최솟값을 삭제해야 한다. -> 정렬이 되있어야 한다.

 

그렇다면 STL multiset를 사용하면 편리하다.

 

multiset을 사용하면 수를 중복해서 삽입할 수 있고, 자동으로 오름차순 정렬을 해준다.

그러므로 최솟값을 꺼내려면 iterator를 사용하여 set의 맨 왼쪽 부분(ms.begin() )을, 

최댓값을 꺼내려면 set의 맨 오른쪽 부분(ms.end() -1 )을 가리키면 된다.

 

코드

#include <bits/stdc++.h>
using namespace std;
multiset<int> ms; // multiset을 사용한다


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

	int t;
	cin >> t; // 테스트 케이스 t 입력

	while (t--) {
		ms.clear(); // ms 초기화
		int k;
		cin >> k; // 연산할 개수 k 입력
		while (k--) {
			char order; // 연산을 나타내는 문자
			int n;
			cin >> order >> n;

			if (order == 'I') { //order가 I라면
				ms.insert(n); // 삽입한다.
			}

			else if (order == 'D') { // order가 D라면
				
				if (ms.size() != 0) { // ms가 비어있지 않다면
					
					if (n == 1) { // n이 1이라면 최댓값을 삭제해야한다.
						auto iter = ms.end();
						iter--;
						ms.erase(iter);
					}
					else if (n == -1) { // n이 -1이라면 최솟값을 삭제해야한다.
						auto iter = ms.begin();
						ms.erase(iter);
					}
				}
				else {

				}
			}
		}
		if (ms.size() == 0) { // 만약 ms가 비어있다면
			cout << "EMPTY" << "\n"; // EMPTY 출력
		}
		else { // ms가 비어있지않다면
			auto itermax = ms.end(); // 최댓값
			itermax--;
			auto itermin = ms.begin(); // 최솟값
			cout << *itermax << ' ' << *itermin << "\n"; // 뒤에 "\n" 넣는걸 깜빡해서 몇 번 틀렸다...
		}
	}
}

 

결과

7662번 결과

STL multiset의 편리함을 몸소 느낄 수 있었던 문제였다.

우선순위 큐를 구현해서 푸는 게 베스트겠지만, multiset을 이용해서도 이 문제를 풀 수 있다는 것을 알면 좋을 것 같다.