(2696) 중앙값 구하기

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

단계별로 풀어보기

26단계(우선순위 큐) 5번째

 

 

 

최대 힙과 최소 힙을 하나씩 선언한 뒤, 입력받을 때마다 양쪽 힙의 개수의 균형을 맞추며 새로운 값을 넣어주면 된다. 단 중앙값을 구하기 위해 최대 힙의 top은 항상 최소 힙의 top보다 작아야 한다.

 

여담으로 출력 결과를 10개씩 끊어 쓰라고 하지만 백준 채점 시스템 상 공백과 줄바꿈을 구분하지 않으므로 굳이 할 필요 없다.

 

 

 

#include <iostream>
#include <queue>
using namespace std;

void solve(){
  int m;
  
  cin >> m;
  
  cout << (m+1)/2 << "\n";
  
  priority_queue<int> maxq;
  priority_queue<int, vector<int>, greater<int>> minq;
  
  for(int i=1;i<=m;i++){
    int n;
    
    cin >> n;
    
    if(i==1){
      maxq.push(n);
      cout << n << " ";
    }else if(i==2){
      if(maxq.top() > n){
        minq.push(maxq.top());
        maxq.pop();
        maxq.push(n);
      }else{
        minq.push(n);
      }
    }else if(i&1){
      if(minq.top() < n){
        maxq.push(minq.top());
        minq.pop();
        minq.push(n);
      }else{
        maxq.push(n);
      }
      cout << maxq.top() << " ";
    }else{
      if(maxq.top() > n){
        minq.push(maxq.top());
        maxq.pop();
        maxq.push(n);
      }else{
        minq.push(n);
      }
    }
  }
  
  cout << "\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int T;
  
  cin >> T;
  
  while(T--)  solve();
  
  return 0;
}