※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※
이번에 볼 문제는 백준 7662번 문제인 이중 우선순위 큐이다.
문제는 아래 링크를 확인하자.
7662번: 이중 우선순위 큐
입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적
www.acmicpc.net
우선순위 큐(priority queue)는 자료의 추가가 수시로 이루어지는 경우, 우선순위가 가장 높은(또는 낮은) 자료를 항상 빠르게 꺼낼 수 있는 자료구조이다.
이 문제에서는 쿼리를 통해 자료를 빈번히 추가하고 우선순위가 가장 높은 자료 또는 가장 낮은 자료를 쿼리가 들어온 시점을 기준으로 제거한다.
이런 작업을 수행할 수 있는 우선순위 큐를 double-ended priority queue라고 한다.
double-ended priority queue를 구현하는 대표적인 방법 중 하나는 min-max heap을 이용하는 것이다.
그러나 이 문제는 자료구조를 처음서부터 코딩하라는 문제가 아니기에 글쓴이는 min-max heap을 직접 구현하지는 않았다.
min-max heap에 관심이 있다면 다음 위키백과 링크를 참고하자.
en.wikipedia.org/wiki/Min-max_heap
글쓴이는 stl에 들어있는 std::priority_queue를 활용하여 문제를 풀었다.
std::priority_queue는 max heap 자료구조인데, 정수 자료의 경우 자료를 넣을 때 -1을 곱해 넣고 꺼낼 때 다시 -1을 곱하는 방식으로 min heap으로도 사용할 수 있다.
(단, 일반적인(signed) int형의 경우 양수와 음수가 완전히 대응되지 않으므로 이에 주의한다.)
문제를 푼 방식은 단순하다.
1) 새로운 정수가 들어온다면 이 정수를 max heap과 min heap에 각각 넣는다.
2-1) 최댓값을 지우라는 명령이 들어오면 max heap에서 최댓값을 지우고, min heap에서 다음에 이 수가 나오면 지워야 한다고 기록해둔다. 이 수들은 min heap에서 숫자가 지워지는 순서대로 만나게 될 것이므로, 또 다른 min heap에 저장해두면 지워야 할 때 쉽게 확인하고 지울 수 있다.
2-2) 최솟값을 지우라는 명령이 들어오면 min heap서 최솟값을 지우고, max heap에서 다음에 이 수가 나오면 지워야 한다고 기록해둔다. 이 수들은 max heap에서 숫자가 지워지는 순서대로 만나게 될 것이므로, 또 다른 max heap에 저장해두면 지워야할 때 쉽게 확인하고 지울 수 있다.
3) max heap과 min heap에서 지워야 할 수를 모두 지운다.
4) 1~3을 반복한다.
아래는 제출한 소스코드이다.
#include <iostream>
#include <queue>
using std::priority_queue;
using std::cin;
using std::cout;
void solve() {
priority_queue<long long> mxpq;
priority_queue<long long> mxpqchk;
priority_queue<long long> mnpq;
priority_queue<long long> mnpqchk;
int k;
cin >> k;
char type;
long long n;
for (int i = 0;i < k;i++) {
cin >> type >> n;
if (type == 'I') {
mxpq.push(n);
mnpq.push(-1*n);
}
else {
if (n == 1 and mxpq.size()!=0) {
long long x = mxpq.top();
mnpqchk.push(-1*x);
mxpq.pop();
}
else if (n == -1 and mnpq.size()!=0) {
long long x = -1*mnpq.top();
mxpqchk.push(x);
mnpq.pop();
}
int sz1 = mxpq.size();
int sz2 = mxpqchk.size();
while (sz1 != 0 and sz2 != 0) {
if (mxpq.top() == mxpqchk.top()) {
mxpq.pop();
mxpqchk.pop();
sz1 = mxpq.size();
sz2 = mxpqchk.size();
}
else break;
}
sz1 = mnpq.size();
sz2 = mnpqchk.size();
while (sz1 != 0 and sz2 != 0) {
if (mnpq.top() == mnpqchk.top()) {
mnpq.pop();
mnpqchk.pop();
sz1 = mnpq.size();
sz2 = mnpqchk.size();
}
else break;
}
}
}
if (mxpq.size()==0) cout << "EMPTY\n";
else cout << mxpq.top() << ' ' << -1*mnpq.top() << "\n";
}
int main()
{
std::ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
for (int i = 0;i < T;i++) {
solve();
}
return 0;
}'BOJ' 카테고리의 다른 글
| [BOJ 14686 // C++] Sum Game (0) | 2021.02.07 |
|---|---|
| [BOJ 1107 // C++] 리모컨 (0) | 2021.02.06 |
| [BOJ 1780 // C++] 종이의 개수 (0) | 2021.02.04 |
| [BOJ 7569 // C++] 토마토 (0) | 2021.02.03 |
| [BOJ 16236 // C++] 아기 상어 (0) | 2021.02.02 |