[백준] 1655 가운데를 말해요 (C++)

백준 1655 가운데를 말해요 문제
백준 1655 가운데를 말해요 소스코드

📄 문제 설명

Problem

<가운데를 말해요>

: 정수 하나씩 외칠 때마다 지금까지 나온 수 중 중간값을 말하는 게임.
만일, 외친 정수의 개수가 짝수개라면 중간에 있는 두 수 중 작은 수를 말해야한다.

Input

첫째 줄 : 정수의 개수 N (1 ≤ N ≤ 100,000)
다음 N개의 줄 : N개의 정수가 차례대로 주어진다. (-10,000 ≤ 정수 ≤ 10,000)

Output

한 줄에 하나씩 N줄에 걸쳐 <가운데를 말해요 게임>의 말해야하는 수를 순서대로 출력한다.

Example Input 1

7
1
5
2
10
-99
7
5

Example Output 1

1
1
2
2
2
2
5

📝 문제 해설

이 문제는 N개의 수가 주어지는데 주어질 때마다 중간값을 출력하는 문제이다.

우선순위 큐로 최대힙(maxHeap)과 최소힙(minGeap)을 만들어 해결하였는데,
문제 해결을 위해 지켜주어야할 규칙이 두가지 있다.

1. maxHeap의 size가 minHeap의 size보다 크거나 같아야한다.
2. maxHeap의 top이 minHeap의 top보다 커야한다.
  (만일, maxHeap의 top이 더 큰 경우 swap)

해당 조건을 만족한다면 항상 maxHeap의 top이 중간 값이 된다.

예를 들어, n이 7이고 정수가 순서대로 1 5 2 10 -99 7 7 일 때 아래와 같다.

maxHeap은 minHeap의 top보다 작은 숫자로만 이루어져 있으며,
maxHeap의 크기가 minHeap의 크기보다 하나가 많거나 같기 때문에
항상 maxHeap의 top값이 중간값이 되고 중간값 중 더 작은 값이 된다.

</> Source Code

#include <bits/stdc++.h>

using namespace std;

int main() {	
	int n;
	scanf("%d", &n);
	
	priority_queue<int, vector<int>, less<int>> maxHeap;
	priority_queue<int, vector<int>, greater<int>> minHeap;
	
	for(int i = 0; i < n; i++){
		int x;
		scanf("%d", &x);
		
		if(maxHeap.size() <= minHeap.size()){
			maxHeap.push(x); 
		}
		else{
			minHeap.push(x);
		}
		
		while(!minHeap.empty() && maxHeap.top() > minHeap.top()){
			int max = maxHeap.top();
			int min = minHeap.top();
			 
			maxHeap.pop();
			minHeap.pop();
			
			maxHeap.push(min);
			minHeap.push(max);
		}
		
		printf("%d\n", maxHeap.top());
		
	}
	
	return 0;
}