백준 1655번: 가운데를 말해요

 

 

 

 

 

 

우선순위 큐를 두개 이용하는 문제였다.

최대힙, 최소힙 두개를 다 사용한다.

 

 

 

그림처럼 최대힙과 최소힙을 정의 하면

q.top()은 항상 중간값이고, pq.top()은 항상 중간값보다 한단계 큰 수가 오게된다.

 

문제는 그걸 유지하는건데 

입력이 들어올 때마다 두개 힙의 사이즈를 조절하면 매우 쉽다.

최대힙이 중간값을 항상 포함하고 있어야하므로 

입력된 수의 갯수가 짝수일 땐 크기가 같아야하고, 홀수일 땐 최대힙(q)이 1만 더 커야한다. 

 

#include <iostream>
#include <queue>
using namespace std;


int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);	//cin 실행속도 향상

	int n;
	cin >> n;
	priority_queue<int, vector<int>, greater<int>> pq; //최소힙 (중간값위)
	priority_queue<int> q; //최대힙 (중간값포함 아래)

	for (int i = 0; i < n; i++) {
		int m;
		cin >> m;
		
		// 둘다비었을 때
		if (q.empty() && pq.empty())	
			q.push(m);
		
		// 하나라도 안비었을 때
		else {	
			if (m <= q.top())
				q.push(m);
			else
				pq.push(m);
		}


		// 최대힙의 크기가 최소힙의 크기보다 1크거나 같도록 조절
		// 최소힙이 최대힙보다 클 때
		if (q.size() < pq.size()) {	
			q.push(pq.top());
			pq.pop();
		}
		//최대힙이 최소힙보다 2 더 클 때
		else if (q.size() > pq.size() + 1) {	
			pq.push(q.top());
			q.pop();
		}

		// 갯수가 짝수일때 최대힙 출력
		// 중간값은 최대힙에 오도록 했으므로 최대힙 출력
		cout << q.top() << "\n";
	}

	return 0;
}