문제 풀이

1년 전쯤에 한번 풀고 다시 푸니까 어떻게 풀었는지 기억이 안났던 문제, 직감상 우선순위 큐를 두 개를 사용해서 풀어야한다고 생각했다.
최대힙, 최소힙을 이용해서
최대힙의 top, 최소힙의 top에 중간값을 후보를 위치할 수 있도록 구현을 한다.
그렇게하려면 최대힙의 원소 전체는 최소힙의 top보다 작아야한다. 즉 최대 힙의 top은 최소힙의 top보다 작아야한다.

ex)
최대힙 | 최소힙
{-1 2 3 | 10 12}
(각각 '|'를 기준으로 왼쪽 오른쪽이 top이다)

그리고 각 원소의 개수의 균형을 맞춰준다.
최대힙은 최소힙보다 원소의 개수를 최대 한개 많도록 유지해준다.
최소힙은 최대힙의 원소 개수보다 같거나 적도록 유지해준다.

그렇게한다면 각 힙의 top에 중간값이 들어가있게되고 그 중 작은값을 출력하면 된다.

문제 링크

boj/1655

소스코드

PS/1655.cpp

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<stack>
#include<map>
#include<memory.h>
#include<queue>
using namespace std;

priority_queue<int> pq;
priority_queue<int, vector<int>, greater<int>> pq2;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;

	
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		
		if (i == 0)
		{
			pq.push(a);
			cout << a << '\n';
		}
		else
		{
			if (a >= pq.top())
			{
				pq2.push(a);
			}
			else
			{
				pq.push(a);
			}
			if ((int)pq.size() - (int)pq2.size() == 2)
			{
				pq2.push(pq.top());
				pq.pop();
			}
			else if ((int)pq2.size() - (int)pq.size() == 1)
			{
				pq.push(pq2.top());
				pq2.pop();
			}
			cout << min(pq.top(), pq2.top())<<'\n';

		}
	}
}