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

해결법

• 최소 힙, 최대 힙 이렇게 두 개의 힙을 이용하면 된다.
  [최대 힙] $\leq$ 중간값 $\leq$ [최소 힙] 이런식으로!
• '중간값'을 출력해야 하므로 양쪽 힙의 밸런스가 중요하다.
  • 최대 힙에는 최소 힙의 top보다 작은 원소들이 들어간다.
    따라서 최소 힙의 top보다 최대 힙의 top이 더 크다면 바꿔주어야 한다.
  • 최대 힙의 크기는 최소 힙의 크기가 같거나 1개 더 많아야 한다.
    근데 어짜피 크기비교해서 작은쪽에 넣어줄거라 1개 더 많은지 2개 더 많은지.. 개수는 체크하지 않았음
    크기가 같다면 최대 힙에 넣어주기~
• 아무튼 이렇게 하면 최대 힙의 top이 가운데 값이 된다.

소스코드

#include <bits/stdc++.h>
using namespace std;

int n;
priority_queue<int> maxHeap;
priority_queue<int, vector<int>, greater<int> > minHeap;


int main() {
  ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);

  cin>>n;
  int a; cin>>a; cout<<a<<"\n"; n--;
  maxHeap.push(a);
  
  while(n--){
    cin>>a;
    if(maxHeap.size()>minHeap.size())
      minHeap.push(a);
    else if(maxHeap.size()<=minHeap.size())
      maxHeap.push(a);

    if(!minHeap.empty() && maxHeap.top()>minHeap.top()){
      int tmp1 = maxHeap.top();
      int tmp2 = minHeap.top();
      minHeap.pop(); minHeap.push(tmp1);
      maxHeap.pop(); maxHeap.push(tmp2); 
    }
    
    cout<<maxHeap.top()<<"\n";
  }
}

제출결과