문제
풀이
- 우선순위 큐 2개를 사용하면 해결할 수 있다. (Max, Min)
- Max에 들어있는 최대값을 중앙값으로 만드는 방식으로 구현
- Max.size() == Min.size() 인 경우 Max에 값을 넣고, 그렇지 않으면 Min에 넣는다.
- Max.top() > Min.top()인 경우, 두 값을 Swap한다.
- 위 2개의 규칙을 사용하면 Max.top()은 계속 중앙값이 유지된다.
코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
priority_queue<int> Max, Min;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (Max.size() == Min.size()) {
Max.push(x);
} else {
Min.push(-x);
}
if (!Max.empty() && !Min.empty()) {
int xx = Max.top();
int yy = -Min.top();
if (xx > yy) {
Max.pop();
Min.pop();
Max.push(yy);
Min.push(-xx);
}
}
cout << Max.top() << '\n';
}
}