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

문제 링크 => 1655번: 가운데를 말해요 (acmicpc.net)

1655번: 가운데를 말해요

---

최소힙, 최대힙을 이용하는 문제이다.

 

우선순위 큐를 이용하여 maxHeap, minHeap를 만들고 최소힙, 최대힙의 합한 갯수, 즉, 받아온 데이터의 갯수가 홀수일때와 짝수일때를 고려해줘야 한다.

 

데이터의 갯수(2n+1)가 홀수일 때 => 최대힙의 갯수 n+1 개, 최소힙의 갯수 n 개에 대하여 최대힙의 최댓값, 최소힙의 최솟값을 비교하여 더 작은 결과가 중간값이다. 

 

데이터의 갯수(2n)가 짝수일 때 => 최대힙, 최소힙의 갯수는 n 개로 동일하며 이 경우 또한 최대힙의 최댓값, 최소힙의 최솟값을 비교하여 더 작은 결과가 중간값이다.

 

이때 주의할 점은, 최대힙에서 최댓값을 최소힙에 넣고 최소힙에서 최솟값을 최대힙에 넣는 과정을 반드시 해주는 것이 필수다.

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#define INF 100000000
#define endl '\n'
#define ll long long

using namespace std;

void solve() {
	
	priority_queue<int> maxHeap, minHeap;

	int n;
	cin >> n;

	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		maxHeap.push(x);

		if (i == 1) {
			cout << x << endl;
		}
		else if (i == 2) {
			minHeap.push(-maxHeap.top());
			maxHeap.pop();
	
			int x = maxHeap.top(), y = -minHeap.top();
			cout << (x < y ? x : y) << endl;
		}
		else {
			if (i % 2) {
				minHeap.push(-maxHeap.top());
				maxHeap.pop();
				maxHeap.push(-minHeap.top());
				minHeap.pop();
				int x = maxHeap.top(), y = -minHeap.top();
				cout << (x < y ? x : y) << endl;
			}
			else {
				minHeap.push(-maxHeap.top());
				maxHeap.pop();
				maxHeap.push(-minHeap.top());
				minHeap.pop();
				minHeap.push(-maxHeap.top());
				maxHeap.pop();
				int x = maxHeap.top(), y = -minHeap.top();
				cout << (x < y ? x : y) << endl;
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	solve();
	
	return 0;
}