[BOJ-7662] 이중 우선순위 큐(C++)

[BOJ-7662] 이중 우선순위 큐(C++)

728x90

백준 7662 이중 우선순위 큐

문제 설명

- 이중 우선순위 큐를 구현하여, 데이터 삽입과 삭제 연산을 구현하라.

- 데이터 삭제 시 우선순위가 가장 높은 것과 가장 낮은 것을 삭제할 수 있다.

- Q에 적용될 연산을 처리한 후 최종적으로 Q에 저장된 데이터 중 최댓값과 최솟값을 출력하라.

- 연산 후 Q가 비어있다면, "EMPTY"를 출력하라.

입력 값

- 테스트 데이터 T가 주어진다.

- 각 테스트 데이터 첫째 줄에는 Q에 적용할 연산의 개수를 나타내는 K가 주어진다.

( K <= 1,000,000 )

- 이어지는 K줄 각각엔 연산을 나타내는 문자('D' 또는 'I')와 정수 n이 주어진다.

- 'I n'은 정수 n을 Q에 삽입하는 연산을 의미한다.

- 'D 1'은 Q에서 최댓값을 삭제하는 연산을 의미한다.

- 'D -1'은 Q에서 최솟값을 삭제하는 연산을 의미한다.

- 최댓값(최솟값)을 삭제하는 연산에서 최댓값(최솟값)이 둘 이상인 경우, 하나만 삭제된다.

- Q가 비어있는데 적용할 연산이 'D' 라면 이 연산은 무시해도 된다.

- Q에 저장될 모든 정수는 32비트 정수이다.

예제

문제 분석

- 이 문제는 우선순위큐를 이용하는 문제이다.

- C++에서 제공하는 multiset을 이용하면, 중복 값을 허용하는 heap 자료구조를 사용할 수 있다.

- 여기서 주의할 점은 노드 삭제 시 값으로 삭제하게 된다면 중복 값이 모두 삭제된다는 점이다.

소스 코드

#include #include #include #include using namespace std; multiset ms; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int tc,t; cin >> tc; for (int i = 0; i < tc; i++) { ms.clear(); cin >> t; char oper; int n; for (int j = 0; j < t; j++) { cin >> oper >> n; if (oper == 'I') { ms.insert(n); } else { if (ms.empty()) { continue; } if (n == 1) { int val = *ms.rbegin(); int cnt = ms.count(val); ms.erase(*ms.rbegin()); if (cnt > 1) { for (int i = 1; i < cnt; i++) { ms.insert(val); } } } else { ms.erase(ms.begin()); } } } if (ms.empty()) { cout << "EMPTY

"; } else { cout << *ms.rbegin() << " " << *ms.begin() << "

"; } } return 0; }

from http://9327144.tistory.com/104 by ccl(A) rewrite - 2021-09-30 22:00:26