[C++] 백준 1655번 가운데를 말해요

문제

백준 1655번 가운데를 말해요

풀이

maxheap와 minheap 2개를 이용해야하는 문제이다.
maxheap에는 minheap과 같거나 1개 많게 숫자를 채우고 maxheap의 최대는 항상 minheap의 최소보다 작게 유지한다.
이 상태에서 maxheap.top()은 항상 입력된 숫자들중 중간이다.

#include <iostream>
#include <vector>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <queue>
#define endl '\n'

using namespace std;

int n;
priority_queue<int> maxheap;
priority_queue<int,vector<int>,greater<int>> minheap;
int arr[100000];

void solve(){
  for (int i=0; i<n; i++){
    if (maxheap.size() == minheap.size()) maxheap.push(arr[i]);
    else minheap.push(arr[i]);

    while (!maxheap.empty() && !minheap.empty() && maxheap.top() > minheap.top()){
      int a = maxheap.top();
      int b = minheap.top();
      maxheap.pop();
      minheap.pop();
      maxheap.push(b);
      minheap.push(a);
    }

    cout << maxheap.top() << endl;
  }
}

int main(){
  ios_base :: sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  // ifstream cin;
  // cin.open("input.txt");

  cin >> n;

  for (int i=0; i<n; i++){
    cin >> arr[i];
  }

  solve();
}