[백준 BOJ][C++]1655번 가운데를 말해요 풀이: Heap

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

1655번: 가운데를 말해요

 

이 문제는 최대 힙, 최소 힙 두 개 모두를 사용하여 해결해야 합니다. 

 

 중앙값을 기준으로 중앙값 이하의 수들은 최대 힙에, 중앙값보다 큰 수들은 최소 힙에 저장하고 이때의 중앙값은 최대 힙의 top 원소가 됩니다. 

 

 힙에 원소를 삽입할 때, 최대 힙과 최소 힙의 원소 개수가 같다면 최대 힙에, 그렇지 않다면 최소 힙에 삽입합니다. 이때 최대 힙과 최소 힙은 중앙값을 기준으로 나누었기 때문에 최대 힙의 원소는 최소 힙의 원소보다 항상 작아야합니다. 때문에 최대 힙의 top이 최소 힙의 top보다 크다면 두 원소를 교환해야 합니다. 

 

(빨간색이 top)	maxHeap	minHeap	중앙값(maxHeap의 top)
1	1		1
5	1	5	1
2	1, 2	5	2
10	1, 2	5, 10	2
-99	-99, 1, 2	5, 10	2
7	-99, 1, 2	5, 7, 10	2
5	-99, 1, 2, 5	5, 7, 10	5

 

 

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstdio>

using namespace std;

int N;
priority_queue<int> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;

void insert(int x) {
	if (maxHeap.size() == 0) {
		maxHeap.push(x);
		return;
	}

	if (maxHeap.size() == minHeap.size()) {
		maxHeap.push(x);
	}
	else {
		minHeap.push(x);
	}

	if (maxHeap.top() > minHeap.top()) {
		maxHeap.push(minHeap.top());
		minHeap.pop();
		minHeap.push(maxHeap.top());
		maxHeap.pop();
	}
}

int main(void) {

	scanf("%d", &N);

	for (int i = 0; i < N; i++) {
		int x;
		scanf("%d", &x);

		insert(x);

		printf("%d\n", maxHeap.top());
	}

	return 0;
}