백준 1655 가운데를 말해요

백준 1655

이 문제는 고민해서 풀어도 여러번 틀려서 다른 분들의 풀이를 참고했다.
최대힙과 최소힙인 두가지 우선순위 큐를 만들고 규칙 2가지에 맞춰서 원소를 삽입하고 최대힙의 top만 확인해주면 답이 된다.
1. 최대힙의 크기는 최소힙의 크기보다 같거나 하나 더 크다.
2. 최대힙의 top에 있는 원소는 최소힙의 top에 있는 원소보다 작거나 같아야 한다.
=> 2 번째 규칙에 위배되면 최대힙의 top 워소와 최소힙의 top 원소를 swap해주면 된다.

bold한 숫자가 top에 있는 원소
ex) 7
1
최대힙 : 1 최소힙:
5
최대힙 : 1 최소힙: 5
2
최대힙 : 1 2 최소힙: 5
10
최대힙 : 1 2 최소힙: 5 10
-99
최대힙 : 1 2 -99 최소힙: 5 10
7
최대힙 : 1 2 -99 최소힙: 5 10 7
5
최대힙 : 1 2 -99 5 최소힙: 5 10 7

#include <bits/stdc++.h>
using namespace std;
int n;
priority_queue<int> maxq;
priority_queue<int, vector<int>, greater<int>>minq;
int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	int n;
	cin >> n;

	while (n--) {

		int x;
		cin >> x;

		if (minq.size() < maxq.size()) {
			minq.push(x);
		}
		else {
			maxq.push(x);
		}

		while (!minq.empty() && !maxq.empty()&& minq.top() < maxq.top()) {
			int a = minq.top();
			minq.pop();
			int b = maxq.top();
			maxq.pop();

			minq.push(b);
			maxq.push(a);
			}

		cout << maxq.top() << '\n';
	}
}