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

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

1655번: 가운데를 말해요

 

요구사항

입력 수 중 중간 값 출력하기

 

풀이

힙을 두개 만들어 중간 값은

max힙의 값이다

1. 수가 홀수 일 때, 중간 값은 maxheap의 탑

2. 수가 짝수 일 때, 중간 값은 maxheap의 탑

 

그러므로 maxheap의 사이즈가 minheap의 사이즈보다 같거나 +1이여야 한다

maxheap과 minheap의 top이 교환 되었을 경우 두 수를 바꾸어 준다

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>
using namespace std;
int n;
vector<int> v;
priority_queue<int> maxq; //최대 힙
priority_queue<int, vector<int>, greater<int>> minq; //최소 힙
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		if (maxq.size() == minq.size()) {
			maxq.push(x);
		}
		else {
			minq.push(x);
		}
		if (maxq.size() != 0 && minq.size() != 0 && maxq.top() > minq.top()) {
			int maxvalue = maxq.top();
			int minvalue = minq.top();
			maxq.pop();
			minq.pop();
			maxq.push(minvalue);
			minq.push(maxvalue);
		}
		printf("%d\n", maxq.top());
	}
}

 

아래 블로그 참조하였다

https://jokimthink.tistory.com/2