백준 1655

가운데 숫자 찾기 c++

 

처음에는 이진 탐색을 이용하여 재귀 호출로 문제를 풀어보려 했자.. 그치만 자꾸 메모리 초과가 나와서 다른 방법을 찾아보니 우선순위 큐를 이용하여 중간 값을 찾을 수 있었다!

 

오름차순으로 정렬한 max heap 과 내림차순으로 정렬한 min heap 을 이용하였다.

priority_queue<int, vector<int>, greater<int>> minheap;

priority_queue<int, vector<int>> maxheap; //비교 함수를 주지 않으면 자동으로 오름차순으로 설정

 

두 힙에 번갈아가며 수를 넣어주는데, min의 top이 max 의 top 보다 더 작은 경우 top을 swap 해준다.

결과적으로 max의 top에는 중간값이 오게 된다!

처음에 숫자를 할당해줄 heap 을 min heap 으로 정해 heap 의 size 가 같다면 중간 값 중에서 작은 값을 소유한 max heap의 top을 출력하고, 아닌 경우에는 중간에 위치하게 되는 숫자인 min의 top을 출력해준다!

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
priority_queue<int, vector<int>, greater<int>> minheap;
priority_queue<int, vector<int>> maxheap;
int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	int n;
	cin >> n;
	for (int i = 0;i < n;i++) {
		int m;
		cin >> m;
		if (i % 2 == 1) {
			maxheap.push(m);
		}
		else {
			minheap.push(m);
		}
		if (!minheap.empty() && !maxheap.empty() && minheap.top() < maxheap.top()) {
			int top=maxheap.top();
			maxheap.pop();
			maxheap.push(minheap.top());
			minheap.pop();
			minheap.push(top);
		}
		if (minheap.size() == maxheap.size()) {
			cout << maxheap.top()<<"\n";
		}
		else {
			cout << minheap.top()<<"\n";
		}
	}
	return 0;
}