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

문제 링크: https://www.acmicpc.net/problem/1655

 

재밌는 문제입니다. 힙을 두 개 쓰면 됩니다.

max heap, min heap을 만든 다음 아래 두 조건을 만족하게 하면 항상 max heap의 top이 중간값(median)이 됩니다.

• 1. max heap의 원소 개수는 min heap과 같거나 min heap보다 1 커야 한다
• 2. max heap의 모든 값은 min heap의 모든 값보다 작거나 같아야 한다

#pragma GCC optimize ("Ofast")

#define _CRT_SECURE_NO_WARNINGS
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING

#include <bits/stdc++.h>
using namespace std;



int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);


	priority_queue<int> max_heap;
	priority_queue<int, vector<int>, greater<int>> min_heap;

	int n;
	cin >> n;
	while (n--) {
		int in;
		cin >> in;

		if (max_heap.size() == min_heap.size())
			max_heap.push(in);
		else
			min_heap.push(in);

		// max heap <= min_heap 만족하는지 체크
		if (!max_heap.empty() && !min_heap.empty() && max_heap.top() > min_heap.top()) {
			auto a = max_heap.top(), b = min_heap.top();
			max_heap.pop(), min_heap.pop();
			max_heap.push(b), min_heap.push(a);
		}

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


	return 0;
}

2번 조건이 만족되지 않을 때마다 각 힙의 top을 빼서 교체해주면 됩니다