[c++] 백준 1655, 가운데를 말해요

백준 1655

알고리즘 분류 : priority queue (우선순위 큐)

정수를 하나씩 입력받을 때마다, 그때의 중간값을 각각 출력하는 문제다. (만약 입력받은 수의 개수가 짝수 개라면, 중간에 있는 두 수 중에서 작은 수를 출력한다.)

두 개의 우선순위 큐를 이용하여 문제를 해결한다.
우선순위 큐 maxheap은 내림차순, minheap은 오름차순 정렬한다.

입력받은 정수를, maxheap의 크기가 minheap의 크기보다 작거나 같은 경우에는 maxheap에 push, 반대의 경우에는 minheap에 push한다. (maxheap의 크기를 minheap의 크기보다 1만큼 크거나 같도록 하기 위함이다.)

push 이후, maxheap의 top이 minheap의 top보다 큰 경우, 서로의 top을 교체해 준다.

int temp1=maxheap.top();
int temp2=minheap.top();
maxheap.pop();
minheap.pop();
maxheap.push(temp2);
minheap.push(temp1);

maxheap의 top이 중간값을 가리키므로, 출력한다.

#include <iostream>
#include <queue>

using namespace std;
priority_queue<int> maxheap;
priority_queue<int,vector<int>,greater<int>> minheap;

void middle(int x){
	if(maxheap.size()<=minheap.size()) maxheap.push(x);
	else minheap.push(x);
	
	if(minheap.size()>0){
		if(maxheap.top()>minheap.top()){ //maxheap의 top이 minheap의 top보다 큰 경우
			int temp1=maxheap.top();
			int temp2=minheap.top();
			maxheap.pop();
			minheap.pop();
			maxheap.push(temp2);
			minheap.push(temp1); //maxheap과 minheap의 top을 교체
		}
	}
	cout << maxheap.top() << '\n';
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N,input;
	cin >> N;
	for(int i=0; i<N; i++){
		cin >> input;
		middle(input);
	}
}