백준 1655 가운데를 말해요

우선순위 큐를 이용하여 이 문제를 풀면 된다.

 

우선순위 큐를 2 개를 운용하는데, 현재까지 말한 숫자들의 부류를 작은 순서대로 정렬한다고 가정할 때, 절반은 작은 부류, 절반은 큰 부류로 나눈다.

 

이렇게 나눌 때 작은 부류는 내림차순이, 큰 부류는 오름차순이 우선순위인 큐로 설정한다.

이렇게 되면 작은 부류의 top 원소는 전체 숫자가 홀수일 때는 가운데 숫자가 되고, 짝수일 때는 가운데 두 수 중에서 작은 숫자가 된다.

 

그러면 출력할 때 항상 작은 부류의 top 원소를 출력하면 정답이 된다.

 

목표한 바 대로 정렬하기 위해서, 첫 번째 원소는 무조건 작은 부류의 우선순위 큐에 넣어줌으로, 작은 부류의 큐가 큰 부류의 큐보다 항상 사이즈가 1이 크도록 설정한다.

 

첫 번째 원소를 넣어주고, 입력받는 숫자를 넣어주는 기준을 잡는다.

 

우선, 두 개의 우선순위 큐의 사이즈가 같으면 무조건 작은 부류의 우선순위 큐에 원소를 넣어준다.

이 때, 넣어주려는 원소가 큰 부류의 top 원소보다 작아야한다. 조건을 만족한다면 작은 부류의 우선순위 큐에 넣어주고, 만약, 큰 부류의 top 원소보다 크면 큰 부류의 top 원소를 작은 부류에 넣어주고, 입력 받은 원소를 큰 부류의 큐에 넣어준다.

 

두 번째로, 두 개의 우선순위 큐 사이즈가 같지 않으면 작은 부류의 큐 사이즈가 더 많다는 것으로 균형을 맞춰주기 위해 무조건 큰 부류의 우선순위 큐에 넣어주어야한다.

하지만 이 때도 마찬가지로 넣어주려는 원소가 작은 부류의 우선순위 큐의 top 원소보다 큰 지 확인해주어야한다. 만약 작다면 위와 방법 처럼 두 원소를 교환해서 각 우선순위 큐에 넣어주면 된다.

 

이렇게 우선순위 큐에 원소를 넣어주면서 항상 작은 부류의 우선순위 큐의 top 원소를 출력해주면 정답이다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <queue>
#include <cmath>

using namespace std;

int main() {
	int N;
	scanf("%d", &N);

	priority_queue<int, vector<int>, greater<int>> bigQ;
	priority_queue<int, vector<int>, less<int>> smallQ;
	for (int i = 0; i < N; ++i) {
		int num;
		scanf("%d", &num);

		if (i == 0) {
			smallQ.push(num);
			printf("%d\n", smallQ.top());
		}
		else {
			if (smallQ.size() == bigQ.size()) {
				if (bigQ.top() <= num) {
					int temp = bigQ.top(); bigQ.pop();
					smallQ.push(temp);
					bigQ.push(num);
				}
				else {
					smallQ.push(num);
				}
			}
			else { // smallQ 사이즈가 더 크다.
				if (smallQ.top() > num) {
					int temp = smallQ.top(); smallQ.pop();
					bigQ.push(temp);
					smallQ.push(num);
				}
				else {
					bigQ.push(num);
				}
			}

			printf("%d\n", smallQ.top());
		}
	}

	return 0;
}