BOJ 7662: 이중 우선순위 큐

www.acmicpc.net/problem/7662

7662번: 이중 우선순위 큐

 

 문제를 간단히 요약하자면 우선순위 큐를 만드는 것인데 특정 원소를 제거하는 연산이 최댓값, 최솟값 두 가지인 우선순위 큐를 만드는 것이다. 예전에 문제를 풀었었는데 아마 github에서 긁어왔던 이중 우선순위 큐 코드를 문제에 맞게 입출력 부분만 고쳐 제출했던 느낌이라 다시 문제를 풀어보았다.

 

 풀이 자체는 굉장히 금방 떠올렸는데 디버깅 작업을 하는데 꽤 오랜 시간을 들여야만 했고 첫 제출에 틀렸습니다를 받고 입력 조건을 보며 머리를 한대 맞은 느낌이었다.

 

 2018년에 틀렸습니다를 받았던 풀이로는 두 개의 우선순위 큐를 이용하여 한 곳에서는 최댓값을, 한 곳에서는 최솟값을 받아오는 방식으로 제출을 했었다. 하지만 이 방법의 경우 두 우선순위 큐 사이에 데이터 동기화가 이루어지지 않아 한쪽에서 빠진 값이 다른 한쪽에서는 남아있기 때문에 다양한 문제가 생길 수 있다. 따라서 데이터 동기화 문제를 해결하기 위해 우선순위 큐에 들어가는 데이터에 label을 달아주는 것을 선택했다. 문제 해결 흐름은 아래와 같다.

1. 각각 최솟값과 최댓값을 관리해주는 이중 우선순위 큐를 만든다. 이때 인자는 하나의 정수가 아닌 pair를 이용하여 실제 데이터와 label을 묶어서 사용한다.
2. 삽입 연산이 들어오면 최솟값을 관리해주는 우선순위 큐에는 데이터의 부호를 반대로, 최댓값을 관리해주는 우선순위 큐에는 데이터를 그대로 넣으며 label은 음수로 넣어준다.
3. 이중 우선순위 큐에 데이터를 삽입할 때 map을 이용하여 삽입된 데이터와 한쌍인 label을 저장한다. map은 key가 정수, value가 큐로 이루어져있다. label은 1부터 차례로 증가하므로 1에서 label이 최솟값부터 나오도록 만들어주면 좋겠다고 생각했다.
4. 삭제 연산이 들어오면 특정 큐의 가장 우선순위가 높은 원소에 붙어있는 label과, 해당 데이터의 큐 맨 앞에 있는 label을 확인하고 만약 같다면 우선순위 큐와 label을 관리하는 큐에서 해당 데이터와 label을 제거하고, 다르다면 같아질 때까지 우선순위 큐에서만 데이터와 label을 제거해준다.
5. 이 작업을 모든 연산에 대해 수행한다.

풀이를 떠올린 순간에 생각보다 간단하게 구현할 수 있을거라 생각했지만 디버깅에 정말 애를 먹었다. 이렇게 구현하여 처음 제출한 코드는 아래와 같다.

#include<bits/stdc++.h>
using namespace std;
int main() {
	int t; scanf("%d", &t);
	while (t--) {
		int k; scanf("%d", &k);
		map<int, queue<int>> chk;
		priority_queue<pair<int, int>> l, h;
		char op[3]; int num;
		int cnt = 1;
		for (int i = 0; i < k; ++i) {
			scanf("%s %d", op, &num);
			if (op[0] == 'I') {
				chk[num].push(cnt);
				l.push({ -num, -cnt });
				h.push({ num, -cnt });
				++cnt;
			}
			else {
				if (~num) {
					while (h.size() && (chk[h.top().first].empty() || chk[h.top().first].front() != -h.top().second))
						h.pop();
					if (h.empty() || chk[h.top().first].empty()) continue;
					if (chk[h.top().first].front() == -h.top().second) {
						chk[h.top().first].pop();
						h.pop();
					}
				}
				else {
					while (l.size() && (chk[-l.top().first].empty() || chk[-l.top().first].front() != -l.top().second))
						l.pop();
					if (l.empty() || chk[-l.top().first].empty()) continue;
					if (chk[-l.top().first].front() == -l.top().second) {
						chk[-l.top().first].pop();
						l.pop();
					}
				}
			}
		}

		while (h.size() && (chk[h.top().first].empty() || chk[h.top().first].front() != -h.top().second))
			h.pop();
		while (l.size() && (chk[-l.top().first].empty() || chk[-l.top().first].front() != -l.top().second))
			l.pop();
		if (l.empty() || h.empty())
			puts("EMPTY");
		else
			printf("%d %d\n", h.top().first, -l.top().first);
	}
}

 위의 코드는 틀렸습니다를 받았다. 정말 생각지도 못한 부분을 놓치고 있었는데 그 조건이 바로 'Q에 저장될 모든 정수는 32-비트 정수'라는 조건이다. 도대체 이 조건 때문에 왜 위의 코드가 틀렸습니다를 받는걸까?

 

 코드를 살펴보면 최솟값을 관리해주는 우선순위 큐는 항상 데이터의 부호를 반대로 바꿔 집어넣고 있다. 이 경우 별다른 선언 없이 쉽게 우선순위 큐의 부호를 바꿔줄 수 있기 때문에 자주 사용하는 방법이다. 하지만 이 방법이 바로 이 문제에서는 문제를 일으켰다. 예를 들어 $-2147483648(-2^{32})$이란 수가 이 큐에 들어가면 어떤 일이 벌어질까? 부호가 반대로 바뀌면 $2147483648(2^{32})$이 되고 이는 부호있는 32비트 정수로는 표현할 수 없는 수이다. C++의 경우 저 값이 다시 $-2147483648$로 돌아오게 되어 문제를 일으킨다. 

 

 재밌게도 이러한 문제를 이용하여 풀 수 있는 문제도 있다.

www.acmicpc.net/problem/15549

15549번: if

 해결방법은 간단하다. 데이터 타입만 64비트 부호있는 정수로 바꿔준다면 쉽게 해결할 수 있다.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
	int t; scanf("%d", &t);
	while (t--) {
		int k; scanf("%d", &k);
		map<ll, queue<int>> chk;
		priority_queue<pair<ll, int>> l, h;
		char op[3]; ll num;
		int cnt = 1;
		for (int i = 0; i < k; ++i) {
			scanf("%s %lld", op, &num);
			if (op[0] == 'I') {
				chk[num].push(cnt);
				l.push({ -num, -cnt });
				h.push({ num, -cnt });
				++cnt;
			}
			else {
				if (~num) {
					while (h.size() && (chk[h.top().first].empty() || chk[h.top().first].front() != -h.top().second))
						h.pop();
					if (h.empty() || chk[h.top().first].empty()) continue;
					if (chk[h.top().first].front() == -h.top().second) {
						chk[h.top().first].pop();
						h.pop();
					}
				}
				else {
					while (l.size() && (chk[-l.top().first].empty() || chk[-l.top().first].front() != -l.top().second))
						l.pop();
					if (l.empty() || chk[-l.top().first].empty()) continue;
					if (chk[-l.top().first].front() == -l.top().second) {
						chk[-l.top().first].pop();
						l.pop();
					}
				}
			}
		}

		while (h.size() && (chk[h.top().first].empty() || chk[h.top().first].front() != -h.top().second))
			h.pop();
		while (l.size() && (chk[-l.top().first].empty() || chk[-l.top().first].front() != -l.top().second))
			l.pop();
		if (l.empty() || h.empty())
			puts("EMPTY");
		else
			printf("%lld %lld\n", h.top().first, -l.top().first);
	}
}