[C++] BOJ-1655

 

문제풀이

---

1. max_heap과 min_heap을 2개 선언한다.

 

2. min_heap의 top이 max_heap의 top보다 작으면 두 우선순위 큐의 탑을 스왑해준다.

 

3. 이 과정을 진행하면 max_heap의 top은 항상 가운데 숫자이기 때문에 max_heap의 top을 출력하면 된다.

(직접 그려보면서 이해하면 쉽다.)

 

 

 

41분 01초

#include <iostream>
#include <queue>
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    priority_queue<int> max_heap;
    priority_queue<int, vector<int>, greater<int> > min_heap;
   int n, num;
   cin >> n;
   
   for(int i = 0; i<n; i++){
      cin >> num;
      if (max_heap.empty())
         max_heap.push(num);
      else if (max_heap.size() == min_heap.size())
         max_heap.push(num);
      else
         min_heap.push(num);
 
      if (!max_heap.empty() && !min_heap.empty() && !(max_heap.top() <= min_heap.top()))
      {
         int a = max_heap.top();
         int b = min_heap.top();
         max_heap.pop();
         min_heap.pop();
         max_heap.push(b);
         min_heap.push(a);
      }
      cout << max_heap.top() << "\n";
   }
}