Boj9426 중앙값 측정
위 문제를 해결하려면
- 중앙값 검색 O(1) 혹은 O(logN)
- 삭제 O(1) 혹은 O(logN) 의 시간안에 가능해야 한다 생각해서 Set 2개를 사용하여 해결하였다.
하나의 set 에는 중앙값보다 작거나 같은수, 다른 하나의 set에는 중앙값보다 크거나 같은수가 들어가도록 유지시켜 중앙값 검색 및 삭제를 O(logN) 시간 안에 해결하였다. 또한 중앙값보다 작거나 같은 값이 들어가는 Set을 set1이라 하고 나머지 하나의 set은 set2라 하면, set1의 size는 set2의 사이즈랑 같거나 1만큼만 크도록 하여야 한다.
#include<iostream>
#include<algorithm>
#include<set>
#include<ctime>
#include<vector>
using namespace std;
multiset<int> s1,s2;
int n, k,arr[250010],before,num2;
long long ans;
void insert(int num) {
if (s1.empty()) {
if(s2.empty()) s1.insert(num);
else {
int num2 = *(s2.begin());
s2.erase(s2.begin());
s1.insert(min(num2, num));
s2.insert(max(num, num2));
}
}
else if (s2.empty()) {
int num2 = *(--s1.end());
s1.erase(--s1.end());
s1.insert(min(num2, num));
s2.insert(max(num, num2));
}
else {
if (s1.size() <= s2.size()) {
num2 = *s2.begin();
s2.erase(s2.begin());
}
else {
num2 = *(--(s1.end()));
s1.erase(--(s1.end()));
}
s1.insert(min(num2, num));
s2.insert(max(num2, num));
}
}
int main() {
scanf("%d %d", &n, &k);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
for (int i = 0; i < n; i++) {
if (i >= k) {
if (!s2.empty() && *(s2.begin()) <= arr[i - k]) {
auto iter = s2.find(arr[i - k]);
s2.erase(iter);
}
else {
auto iter = s1.find(arr[i - k]);
s1.erase(iter);
}
}
insert(arr[i]);
if(i>=k-1) ans += (long long)*(--(s1.end()));
}
printf("%lld", ans);
}