[C++] 백준 1655번 가운데를 말해요

우선순위 큐 문제입니다.

가운데 값을 구하기 위해
우선순위 큐를 두개 만들어 주었습니다.

pqMin : 작은 값들 저장 (내림차순)
pqMax : 큰 값들 저장 (오름차순)

새로운 값이 들어왔을 때 pqMax.top보다 크면 pqMax에 넣어주고
pqMin.top보다 작으면 pqMin에 넣어줍니다.

만약 넣고나서 아래의 조건이 성립하지 않으면

1. pqMax == pqMin + 1
2. pqMax == pqMin

많은 쪽에서 적은쪽으로 top의 위치의 숫자를 옮겨 줍니다.

 

#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

int main(int argc, char *argv[])
{
	int n;
	int num;
	priority_queue<int, vector<int>, greater<int> > pqMax;
	priority_queue<int> pqMin;

	scanf("%d", &n);

	while (n--) {
		scanf("%d", &num);

		if (pqMin.empty() || pqMin.top() >= num) {
			pqMin.push(num);
			if (pqMin.size() > pqMax.size() + 1) {
				pqMax.push(pqMin.top());
				pqMin.pop();
			}
		}
		else if (pqMax.empty() || pqMax.top() <= num) {
			pqMax.push(num);
			if (pqMax.size() > pqMin.size()) {
				pqMin.push(pqMax.top());
				pqMax.pop();
			}
		}
		else if (pqMin.size() <= pqMax.size()) {
			pqMin.push(num);
		}
		else if (pqMin.size() > pqMax.size()) {
			pqMax.push(num);
		}

		printf("%d\n", pqMin.top());
	}

	return 0;
}