백준 1655번 가운데를 말해요 문제풀이(C++)

1655번 가운데를 말해요

아이디어

가운데를 말한다 -> 우선순위 큐 2개 생성 ->
숫자가 1 ~ 10 이라 했을 때
왼쪽 우선순위큐에 1~5 삽입
오른쪽 우선순위 큐에 6~10 삽입
개수를 n/2개 유지 (홀수일때 왼쪽이 n/2 + 1개)

문제풀이

#include<bits/stdc++.h>
using namespace std;
#define MAX 1010
#define INF 2147483647

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	priority_queue<int, vector<int>, greater<>> pqRight;
	priority_queue<int, vector<int>, less<>> pqLeft;
	int n; cin >> n;
	int num; cin >> num;
	n--;
	cout << num << '\n';
	pqLeft.push(num);
	for (int i = 1; i <= n; i++) {
		cin >> num;
		if (pqLeft.size() <= pqRight.size()) {
			if (pqRight.top() < num) {
				pqLeft.push(pqRight.top());
				pqRight.pop();
				pqRight.push(num);
			}
			else
				pqLeft.push(num);
		}
		else{
			if (pqLeft.top() > num) {
				pqRight.push(pqLeft.top());
				pqLeft.pop();
				pqLeft.push(num);
			}
			else
				pqRight.push(num);
		}
		cout << pqLeft.top() << '\n';
	}
	
	return 0;
}