1655

숫자 여러 개를 연속적으로 입력받을 때, 입력받을 때마다 가운데에 있는 숫자를 출력하는 문제이다.

 

Naive 한 방법은 숫자를 입력받을 때마다 정렬하는 방법이다. 그러면, 1=<k<=N 일 때 시그마 (KlogK) 만큼 걸리기 때문에 시간복잡도는 대략 O(N^2)이다.

 

다른 방법은 '가운데'의 성질을 이용하는 방법이다.

숫자들을 반으로 쪼개보자. 예를 들어, 숫자를 짝수개 가지고 있는데 여기에 하나의 숫자를 더 추가한다고 생각해보자. (짝수->홀수) 이때, 가운데 숫자들의 후보들이 결정된다. 즉, 후보들은 짝수개 숫자들을 정렬했을 때 가운데에 근접해 있는 두 숫자와 이번에 추가하는 숫자이다.   

따라서, 이 후보들간의 대소 비교만 잘 조율해서 답을 도출하면 된다.

 

구체적으로 구현을 설명해보면, 일단 priority_queue l(eft), priority_queue<greater<int>>r(ight)를 이용한다. 

후보 : l.top() , r.top()          (새 숫자를 둘 중에 넣었다고 했을 때)

중요한 것은 가운데 숫자는 항상 l.top()이 되게 하는 것이다.

규칙은 다음과 같다.

 

         1. l.size()==r.size() or l.size()==r.size()+1 (짝수, 홀수)

         2. l.top()<=r.top()

 

 

---

 

#include <iostream>
#include <queue>
using namespace std;
priority_queue<int> l;
priority_queue<int> r;
int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int N; cin>>N;
	for(int i=0;i<N;i++){
		int n;cin>>n;
		if(i%2==0) l.push(n);
		else r.push(-n);
		if(!r.empty()&&l.top()>-r.top()) {
			int x=l.top(),y=-r.top();
			l.pop();r.pop();
			l.push(y);r.push(-x);
		}
		cout<<l.top()<<'\n';
	}
	return 0;
}