#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#define ll long long
using namespace std;
int N;
priority_queue<int, vector<int>, greater<int>> minPQ;
priority_queue<int, vector<int>, less<int>> maxPQ;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N;
for(int i=0;i<N;i++)
{
int a;
cin >> a;
if(maxPQ.size() == minPQ.size()){
maxPQ.push(a);
}else{
minPQ.push(a);
}
if(!maxPQ.empty() != 0 and !minPQ.empty() and maxPQ.top() > minPQ.top()){
int maxVal = maxPQ.top(); maxPQ.pop();
int minVal = minPQ.top(); minPQ.pop();
maxPQ.push(minVal);
minPQ.push(maxVal);
}
cout << maxPQ.top()<< '\n';
}
return 0;
}
- 로직
2개의 우선순위 큐
(최대힙-maxPQ
, 최소힙-minPQ
)을 생성
maxPQ
부터 시작
해서 번갈아가면서 값을 넣는다
- 만약
maxPQ.top() <= minPQ.top()
을 만족하지 않으면
값
을 swap
한다
: 최대힙 큐의 top
은 항상 최소힙 큐의 top
보다 작아야 함
- 느낀 점
논리적으로 유추
하듯 풀어낼 수 는 없는 문제였다
두개의 우선순위 큐
를 통해 중간값
을 O(N)
보다 작은 시간
으로 구하는 방법
이 있다는 것 정도만 인지