급하게임개발

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

이 문제는 나의 부족한 머리로는 혼자 생각 할 수 없는 알고리즘이었다.

하지만 이번 문제를 푼 것을 계기로 똑같은 유형의 문제는 틀리지 않아야 겠다.

일단 풀이는 우선순위 큐 2개로 중간 값을 구하는 방법을 알아야 한다

이게 알파이자 오메가였다.

우선순위 큐로 2개의 값을 구하는 방법은

1. MaxHeap은 무조건 MinHeap보다 사이즈가 하나 커야 한다.

2. MaxHeap의 최대값은 MinHeap의 최솟값 보다 작아야 한다. 이 조건을 만족하지 않을 시

maxHeap의 최대값과 MinHeap의 최솟값을 swap해준다.

이 법칙을 지키면 MaxHeap의 최대값은 항상 중간값이 된다.

이 풀이를 위의 문제에서 주어진 예제에 대해서 대입해보겠다.

이런 순서대로 트리가 차면서 항상 Maxheap의 최대값이 중간값을 나타내고 있다. 

코드는 아래와 같다

#include <iostream>
#include <queue>
using namespace std;
priority_queue<int,vector<int>,less<int>> maxq;
priority_queue<int, vector<int>, greater<int>> minq;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int N;
	cin >> N;
	int inputNum;
	cin >> inputNum;
	maxq.push(inputNum);
	cout << maxq.top() << '\n';
	for (int i = 1; i < N; i++) {
		cin >> inputNum;
		if (maxq.size() == minq.size())
			maxq.push(inputNum);
		else {
			minq.push(inputNum);
		}
		if (!maxq.empty() && !minq.empty() && !(maxq.top() < minq.top())) {
			int a = maxq.top();
			int b = minq.top();

			maxq.pop();
			minq.pop();

			minq.push(a);
			maxq.push(b);
		}
		cout << maxq.top()<<'\n';
	}
}

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

이 문제는 한동안 다른프로젝트를 진행하다가 다시 알고리즘을 풀면서 우선순위 큐에 대해 공부해야할 필요성이 있을거 같아 풀기 시작한 문제이다 이 문제의 경우 처음에 이중 우선순위 큐라는 자료구조를 직접 클래스로 작성할 까 생각하다가 메모리제한과 시간제한이 여유로운 것을 보고 최대값 우선순위 큐와 최솟값 우선순위 큐를 2개를 사용하여 풀면 될 것 같은 생각을 했다 이에 그렇게 구현 하여 작성했

#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
priority_queue<int, vector<int>, greater<int>> pqMin;
priority_queue<int, vector<int>> pqMax;
map<int, int>cnt;
void insertpq(int n) {
	pqMax.push(n);
	pqMin.push(n);
	cnt[n]++;
}
void deleteMin() {
	if (!pqMin.empty()) {
		cnt[pqMin.top()]--;
		pqMin.pop();
	}
	while (!pqMax.empty() && cnt[pqMax.top()] == 0) {
		pqMax.pop();
	}
}
void deleteMax() {
	if (!pqMax.empty()) {
		cnt[pqMax.top()]--;
		pqMax.pop();
	}
	while (!pqMin.empty() && cnt[pqMin.top()] == 0) {
		pqMin.pop();
	}
}

int main() {

	int T, n, k;
	char mode;
	cin >> T;
	for (int i = 0; i < T; i++) {
		while (!pqMax.empty()) {
			pqMax.pop();
		}
		while (!pqMin.empty()) {
			pqMin.pop();
		}

		cnt.clear();

		cin >> k;
		for (int i = 0; i < k; i++) {
			cin >> mode >> n;
			if (mode == 'I') {
				insertpq(n);
			}
			else {
				if (n == 1)
					deleteMax();
				else
					deleteMin();
				while (!pqMax.empty() && cnt[pqMax.top()] == 0) {
					pqMax.pop();
				}
				while (!pqMin.empty() && cnt[pqMin.top()] == 0) {
					pqMin.pop();
				}
			}
		}
		if (pqMax.empty() || pqMin.empty()) {
			cout << "EMPTY\n";
		}
		else cout << pqMax.top() << " " << pqMin.top() << '\n';
	}
	return 0;
}

이문제의 경우 가장 중요한건  최솟값 우선순위 큐와 최댓값 우선순위 큐를 계속 동기화를 시켜줘야 한다 즉 최댓값 우선순위 큐에서 삭제한 데이터는 후에 최솟값 우선순위 큐에서도 삭제를 해줘야한다. 또한 이 문제의 경우 여러개의 테스트 케이스를 한번에 입력함으로 각각의 테스트 케이스 마다 우선순위 큐를 초기화 시켜줘야한다 이에

		while (!pqMax.empty()) {
			pqMax.pop();
		}
		while (!pqMin.empty()) {
			pqMin.pop();
		}

이 부분을 작성해서 매 테스트 케이스 마다 초기화 시켜주었다 그후 2번째로 중요한 부분은

void deleteMin() {
	if (!pqMin.empty()) {
		cnt[pqMin.top()]--;
		pqMin.pop();
	}
	while (!pqMax.empty() && cnt[pqMax.top()] == 0) {
		pqMax.pop();
	}
}
void deleteMax() {
	if (!pqMax.empty()) {
		cnt[pqMax.top()]--;
		pqMax.pop();
	}
	while (!pqMin.empty() && cnt[pqMin.top()] == 0) {
		pqMin.pop();
	}
}

이 두 부분이다 이 두부부느이 경우 각자의 우선순위 큐에서 데이터를 지울때 일차적으로 데이터를 동기화 시켜주기 위함이다 만약 어느 한쪽에서의 값을 지웠을 경우 cnt의 값이 0이되있을 것이므로 반대쪽에 큐에서 cnt가 0인 부분들을 pop해줄수 있게 하기위해서다