두 개의 우선순위 큐를 써서 중앙값 찾기

어떤 숫자들의 입력이 계~속 주어진다.

 

들어온 입력들에 대해서 중앙값을 계속 반환해야 한다.

 

자 그럼 이걸 어떻게 해볼까?

 

들어온 입력을 계속 push 하고 정렬을 한다?

-> N번 동안 N 크기의 배열을 정렬하므로 N^2logN  . 따라서 시간 초과가 될 수 밖에 없다.

 

우리가 원하는 건 "중앙값"이다. 구체적으로 전체가 어떻게 정렬되어 있는지는 관심이 없다.

중앙값을 T 라고 했을 때, T는 정렬된 List 에서 가운데에 위치해야 한다.

 

하지만, 정렬을 다해주면 시간 초과. 그래서 정답 T에 대해 배열을 다음과 같이 나눠보자.

1. 무조건 작은 쪽 -> LEFT

2. 무조건 큰 쪽 -> RIGHT

 

LEFT에 있는 모든 애들은 RIGHT 보다 반드시 작아야 한다.

 

그래서 LEFT를 최대힙으로 설정. RIGHT를 최소힙으로 설정해보자

LEFT의 TOP 은 RIGHT의 TOP 보다 항상 작도록 유지 (만약 어길 시 교환)

그럼 LEFT의 TOP 이나 RIGHT의 TOP 중 하나가 답이 될 것이다 -> 세부사항은 문제 따라 다름!

 

이 문제를 풀어보자

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

 

코드는 다음과 같다.

 

#include<iostream>
#include<vector>
#include<queue>
#include<vector>
using namespace std;
int main() {
	cin.tie(0);
	cin.sync_with_stdio(false);
	int N;
	cin >> N;
	priority_queue<int, vector<int>, less<int>> left;
	priority_queue<int, vector<int>, greater<int>> right;
	vector<int> answers;
	for (int i = 0; i < N; i++) {
		int temp;
		cin >> temp;
		// 일단 push. 하지만 길이는 하나만 차이나도록 해주자. (교환이 의미있도록)
		if (i% 2 == 0) {
			left.push(temp);
		}
		else {
			right.push(temp);
		}
		// 교환
		if (left.size() > 0 && right.size() > 0) {
			int leftTop = left.top();
			int rightTop = right.top();
			if (leftTop > rightTop) {
				// 야 이거 역전이다 즉시 교환
				left.pop();
				right.pop();
				left.push(rightTop);
				right.push(leftTop);
			}
		}

		// 정답 찾기 -> 왼쪽 끝
		answers.push_back(left.top());
	}
	for (int i : answers) {
		cout << i << "\n";
	}
	return 0;
}