백준 7662 _ 이중 우선순위 큐

www.acmicpc.net/problem/7662

7662번: 이중 우선순위 큐

---

✨ 내 소스 코드

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

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

	int T, k, n;
	char c;
	cin >> T;
	while (T--) {
		multiset <int> pq;
		cin >> k;
		while (k--) {
			cin >> c >> n;
			if (c == 'I') {
				pq.insert(n);
			}
			else {
				if (pq.empty())continue;
				if (n == -1) {
					pq.erase(pq.begin());
				}
				else {
					pq.erase(--pq.end());
				}
			}

		}
		if (pq.empty()) {
			cout << "EMPTY\n";
		}
		else {
			cout << *(--pq.end()) << " " << *pq.begin() << '\n';
		}
	}
	

	return 0;
}

 

🙏 문제 풀이

위 문제를 풀기 위해서 multiset이라는 자료구조를 선택하였다

set은 key(원소)들의 집합으로 값들이 자동 정렬된다는 특징이 있다

key값이기 때문에 중복이 허용되지 않는다는 특징이 있지만,

multiset의 경우 중복을 허용시켜주기때문에, 중복 값도 허용이 되고 자동 정렬도 되는 multiset을 사용하게 된 것이다

 

multiset을 이용하여 값을 넣고, 문제의 조건에 따라 D -1이면 최솟값을 D 1이면 최댓값을 삭제하는 과정을 반복하였다

모든 작업이 끝나고 pq가 비어있다면 'EMPTY'라는 문자를, 비어있지 않다면 최댓값과 최솟값을 출력하였다

 

 

🌱 최댓값

pq.erase(--pq.end()); //최댓값 삭제
*(--pq.end()) // 최댓값

 

최댓값을 구할때, 위와 같이 --pq.end()라는 식으로 코드를 작성하였는데

이는 pq.end()를 하면 마지막 부분에 대한 주소 값 반환을 반환하는 것은 맞지만 정확히는 마지막 뒤 공백구간를 반환하게 된다

따라서 '--' 처리를 해주어서 공백 전의 마지막 값이 담긴 주소값을 반환하도록 한 것이다

 

prev(pq.end()) == pq.end()-- == --pq.end()

 

⭐ 문제 풀이 결과