백준 1655

 

https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

이 문제는 나의 부족한 머리로는 혼자 생각 할 수 없는 알고리즘이었다.

하지만 이번 문제를 푼 것을 계기로 똑같은 유형의 문제는 틀리지 않아야 겠다.

일단 풀이는 우선순위 큐 2개로 중간 값을 구하는 방법을 알아야 한다

이게 알파이자 오메가였다.

 

우선순위 큐로 2개의 값을 구하는 방법은

1. MaxHeap은 무조건 MinHeap보다 사이즈가 하나 커야 한다.

2. MaxHeap의 최대값은 MinHeap의 최솟값 보다 작아야 한다. 이 조건을 만족하지 않을 시

maxHeap의 최대값과 MinHeap의 최솟값을 swap해준다.

 

이 법칙을 지키면 MaxHeap의 최대값은 항상 중간값이 된다.

이 풀이를 위의 문제에서 주어진 예제에 대해서 대입해보겠다.

이런 순서대로 트리가 차면서 항상 Maxheap의 최대값이 중간값을 나타내고 있다. 

코드는 아래와 같다

#include <iostream>
#include <queue>
using namespace std;
priority_queue<int,vector<int>,less<int>> maxq;
priority_queue<int, vector<int>, greater<int>> minq;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int N;
	cin >> N;
	int inputNum;
	cin >> inputNum;
	maxq.push(inputNum);
	cout << maxq.top() << '\n';
	for (int i = 1; i < N; i++) {
		cin >> inputNum;
		if (maxq.size() == minq.size())
			maxq.push(inputNum);
		else {
			minq.push(inputNum);
		}
		if (!maxq.empty() && !minq.empty() && !(maxq.top() < minq.top())) {
			int a = maxq.top();
			int b = minq.top();

			maxq.pop();
			minq.pop();

			minq.push(a);
			maxq.push(b);
		}
		cout << maxq.top()<<'\n';
	}
}