1655 가운데를 말해요

문제 링크

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

풀이

최대힙 하나 최소힙 하나를 선언한다. 나는 l(left), r(right)라고 이름붙인 힙들을 선언했다. l에는 중간값 이하의 값, r에는 중간값을 초과하는 값들을 저장할 것이기 때문이다. 순서대로 수를 받으면서 l에 하나, r에 하나, 다시 l에 하나, r에 하나... 순서로 push한다. 이 때, 왼쪽에는 반드시 중간값 이하의 값들이 들어가야 하므로, l.top()이 r.top보다 커지면 두 값을 바꾸어 주어야 한다. 이 방식으로 계속 저장해 가면서 l.top()을 출력해 주면 된다. (l.top()에는 항상 중간값 이하의 값에서 가장 큰 값이 저장되어 있으므로)
아니면 다른 방법으로는 새로 받아온 값이 l.top()보다 크다면 r에 push하고, l과 r의 크기를 비교해서 l.size()가 r.size()보다 항상 크거나 같도록 조정해 주면 된다. (l.top() 값 r에 넣고 l.pop()하거나 그 반대로 하면 됨) 출력은 마찬가지로 l.top()값을 계속 출력해 주면 된다.

C++ 코드

#include <iostream>
#include <queue>
#define endl '\n'

using namespace std;

priority_queue<int> l;
priority_queue<int, vector<int>, greater<int>> r;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int N; cin>>N;
    for(int i=0; i<N; i++){
    	int num;
    	cin>>num;
    	if(l.size() == r.size()){
    		l.push(num);
    		if(!r.empty() && l.top()>r.top()){
    			int tmp = l.top();
				l.pop();
				l.push(r.top());
				r.pop();
				r.push(tmp);
			}
		}
		else{
			r.push(num);
			if(l.top()>r.top()){
    			int tmp = l.top();
				l.pop();
				l.push(r.top());
				r.pop();
				r.push(tmp);
			}
		}
		cout<<l.top()<<endl;
	}
    
    return 0;
}