[백준 7662번] 이중 우선순위 큐 (골드4) - C언어(C++)

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

7662번: 이중 우선순위 큐

문제

이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다. 

정수만 저장하는 이중 우선순위 큐 Q가 있다고 가정하자. Q에 저장된 각 정수의 값 자체를 우선순위라고 간주하자. 

Q에 적용될 일련의 연산이 주어질 때 이를 처리한 후 최종적으로 Q에 저장된 데이터 중 최댓값과 최솟값을 출력하는 프로그램을 작성하라.

 

 

---

 multiset을 사용하는 문제이다. 이전에 사용했었는데 잊고 있었다ㅠ 기록이 필요할 것 같다.

 문제를 보자마자 너무나도 직관적으로 최댓값과 최솟값을 구하는 힙으로 구현하는 두 개의 우선순위 큐 구현이 떠올랐다. 그러나, 'D' 명령어에 1이 들어오면 큐 내부의 최댓값을 삭제해야하는데, 최대힙에서는 가장 첫 번째 요소를 삭제할 수 있지만, 최소힙의 가장 뒤에 있을 최댓값을 우선순위 큐로는 삭제할 수 없었다. 결국, 막혀서 검색하다 multiset의 개념을 발견했다.

 

 multiset

• C언어에서의 헤더파일: #include <set>
• 일반 set: 중복 허용 불가. 정렬됨
• 일반 set과 비슷하나, 중복을 허용한다는 차이점이 있다.
• 기본적으로 오름차순 정렬이다.
• 함수: insert, clear, begin(), end(), count(n), size()
• 기본 선언: multiset<int> ms;

 

  힙을 이용한 우선순위 큐를 이용할 때 가장 문제가 문제가 되는 부분은 iterator의 가장 마지막 요소값을 삭제하는 과정이다. 이를 위해 선언 지정자인 "auto" 자료형을  이용하였다. auto 자료형은 초기화시에 초기화 값에 맞춰 자동으로 자료형을 판단하는 기능을 가진다. 이를 통해 가장 multiset 내부의 끝나는점 리턴값 iterator를 얻은 후 해당 위치를 한 칸 앞으로 이동한 곳, 즉 가장 마지막 원소가 있는 위치를 삭제할 수 있었다.

 

 

<< 전체 코드 >>

#include <iostream>
#include <set>

using namespace std;

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

	int t, k, n;
	char c;
	cin >> t;
	while (t--) {
		multiset<int> ms; // default: 오름차순 정렬
		cin >> k;
		while (k--) {
			cin >> c >> n;
			if (c == 'I') 
				ms.insert(n);
			else {
				if (ms.empty())
					continue;
				if (n == -1) ms.erase(ms.begin()); // 가장 앞 위치 삭제
				else {
					auto iter = ms.end(); 
					ms.erase(--iter); // 가장 뒤 원소가 있는 위치 삭제
				}
			}
		}
		if (ms.empty()) cout << "EMPTY" << '\n';
		else {
			auto iter = ms.end();
			iter--;
			cout << *iter << ' ' << *ms.begin() << '\n';
		}
	}
	return 0;
}