1655 가운데를 말해요

---

문제

• 숫자가 순서대로 주어질 때 각 주어진 숫자들 중 가운데의 숫자를 출력

입력

• 숫자의 개수 N (1<= N <=100000)
• 각 숫자의 범위는 -10000 ~ 10000

출력

• 숫자가 주어질 때 마다 주어진 숫자들 중 가운데 숫자를 출력한다.
  짝수의 경우 더 작은 숫자 출력

---

우선순위 큐를 두개 이용하여 문제를 해결했다.
처음에 숫자를 하나 받고 그것을 중앙값으로 저장한다.
다음부터는 다음 규칙을 따른다.

• 중앙값보다 크거나 같은 숫자가 주어진다면 최소힙에 저장
• 숫자가 현재 중앙값보다 작은 숫자가 주어진다면 최대힙에 저장

출력시에는 현재 주어진 총 개수에 따라 중앙값을 적절하게 조정한다.

• 만약 최소힙의 크기가 최대힙보다 1을 초과하여 크다면 중앙값을 최대힙에 넣고 최소힙에서 하나를 꺼내 중앙값으로 만들어 준다.
• 만약 최대힙의 크기가 최소힙보다 1을 초과하여 크다면 중앙값을 최소힙에 넣고 최대힙에서 하나를 꺼내 중앙값으로 만들어 준다.
• 만약 현재까지 주어진 수가 짝수인데 최소힙의 크기가 최대힙보다 1만큼 작다면 중앙값을 최대힙의 값과 교체해준다.

---

정답코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	int key, n;
	cin >> n;

	priority_queue<int>left;
	priority_queue<int,vector<int>, greater<int>>right; 

	cin >> key;
	cout << key << '\n';
	for (int i = 1; i < n; i++) {
		int a;
		cin >> a;
		if (a >= key)right.push(a);
		else left.push(a);
		if (right.size() - left.size() >= 0 && right.size() - left.size() <=1) {
			cout << key << '\n';
		}
		else if (left.size() - right.size() <= 1 && (left.size() - right.size() >= 0 && (left.size() + right.size()) % 2 == 0)) {
			cout << key << '\n';
		}
		else {
			if (right.size() > left.size()) {
				left.push(key);
				key = right.top();
				right.pop();
			}
			else {
				right.push(key);
				key = left.top();
				left.pop();
			}
			cout << key << '\n';
		}
	}

	return 0;
}