백준 1655 가운데를 말해요

www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

단계별로 풀기에서 힙을 공부하고 응용 겸 풀어본 문제이다.

처음에는 이거 벡터로 해야되는거 아닌가? 싶을 정도로 접근이 안돼서 다른 사람의 풀이를 참고했다.

 

최대 힙과 최소 힙을 조건에 맞게 나눠서 그때 그때 최대 힙의 top을 출력해주면 된다.

 

•  최대힙의 크기는 최소 힙의 크기와 같거나 1만큼만 커야 한다.
•  최대힙의 top은 최소 힙의 top보다 작아야 한다.

이 두 조건을 만족시키며 구현하면 된다.

 

#include <iostream>
#include <queue>
using namespace std;

priority_queue<int, vector<int>, greater<>> Min; //최소힙
priority_queue<int> Max;

//1. 최대힙의 크기와 최소힙의 크기는 같거나 1만큼만 커야함
//2. 최대힙의 top은 최소힙의 top보다 작아야함

int main() {
	ios::sync_with_stdio(false); cin.tie(0);

	int n, x;
	cin >> n;
	while (n--) {
		cin >> x;
		if (Max.size() > Min.size()) Min.push(x); 
		else Max.push(x);

		if (!Max.empty() && !Min.empty()) {
			if (Max.top() > Min.top()) {
				int Max_tmp = Max.top();
				int Min_tmp = Min.top();
				Max.pop(); Min.pop();
				Max.push(Min_tmp); Min.push(Max_tmp);
			}
		}
		cout << Max.top() << '\n';
	}
	return 0;
}