출처: https://cses.fi/problemset/task/1076
문제 설명
You are given an array of n integers. Your task is to calculate the median of each window of k elements, from left to right.
The median is the middle element when the elements are sorted. If the number of elements is even, there are two possible medians and we assume that the median is the smaller of them.
입력
The first input line contains two integers n and k: the number of elements and the size of the window.
Then there are n integers x_1,x_2,…,x_n : the contents of the array.
출력
Print n−k+1 values: the medians.
입력 예
출력 예
제약조건
- 1 <= k <= n <= 2x10^5
- 1 <= x_i <= 10^9
문제 풀이 내용
입력 배열을 읽어 들인다.
- 윈도우 크기가 1인 경우는 배열을 순서대로 출력한다.
- 윈도우의 크기가 배열 크기와 같은 경우에는 정렬하여 중간값을 출력한다.
처음에 작성한 알고리즘 - 같은 값이 여러개 있고, 그것들이 중간값인 경우에 잘못된 값을 출력한다.
배열의 앞에서부터 윈도우 크기만큼 multiset 에 넣고, 첫번째 중간값을 출력한다. 새로운 입력값(a), 현재 중간값(b), 삭제할 값(c)을 비교해서, 새로운 중간값을 출력한다.
- 삭제할 값이 중간값과 같은 경우, 새로운 값의 크기에 따라 중간값 위치를 움직인다
- a = b, c > b -> b* = b+1, c < b -> b* = b-1
- 새로운 값과 삭제할 값이 다른 쪽에 위치하면 중간 값을 움직인다.
- a < b && c >= b -> b* = b+1, a >= b && c < b -> b* = b-1.
변경한 알고리즘 - median을 중심으로 커지는 것과 작아지는 2개의 priority_queue 2개를 사용한다.
입력을 median을 기준으로 작은쪽에 넣고, 양쪽 크기를 비교해서 같도록 값을 옮겨준다. 커지는 queue의 값이 median이 된다.
프로그램 내용
같은 값이 여러개 있고, 그것들이 중간값인 경우에 에러가 나오던 소스
더보기
...
vector <long> num_arr(nNum);
multiset <long> sub_arr;
for(int idx=0; idx < nNum; ++idx)
cin >> num_arr[idx];
if (wSize == 1)
for (int idx = 0; idx < nNum; ++idx)
cout << num_arr[idx] << " ";
cout << endl;
return 0;
else if (wSize == nNum)
sort(num_arr.begin(), num_arr.end());
cout << num_arr[(nNum+1) / 2-1] << endl;
return 0;
else
for (int idx = 0; idx < wSize ; ++idx)
sub_arr.insert(num_arr[idx]);
auto med = sub_arr.begin();
/// first median
for (int idx = 0; idx < (wSize-1)/2 ; ++idx)
++med;
cout << *med << " ";
/// moving window
for (int idx = wSize, id=0; idx < nNum; ++idx, ++id)
sub_arr.insert(num_arr[idx]);
if (sub_arr.find(num_arr[id]) == med)
if ( num_arr[idx] < *med)
--med;
else if ( num_arr[idx] >= *med)
++med;
else
if (num_arr[id] < *med && num_arr[idx] >= *med)
++med;
else if (num_arr[id] >= *med && num_arr[idx] < *med)
--med;
sub_arr.erase(sub_arr.find(num_arr[id]));
cout << *med << " ";
...
오름차순, 내림차순으로 priority queue 2개 만들어서 새로운 값들을 넣으면서 중간값을 출력하는 소스
더보기
...
vector<long> num_arr(tN+1);
priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> lpq;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> rpq;
long mid = (tK+1)/2 ;
int w_size = 0;
for(int id=1; id <= tN;++id)
cin >> num_arr[id];
while (!lpq.empty() && lpq.top().second <= id - tK) lpq.pop();
while (!rpq.empty() && rpq.top().second <= id - tK) rpq.pop();
if (w_size < mid)
rpq.push(make_pair(num_arr[id], id));
auto tmp = rpq.top();
rpq.pop();
lpq.push(tmp);
++w_size;
else
lpq.push(make_pair(num_arr[id], id));
auto tmp = lpq.top();
lpq.pop();
rpq.push(tmp);
while (!lpq.empty() && lpq.top().second <= id - tK) lpq.pop();
while (!rpq.empty() && rpq.top().second <= id - tK) rpq.pop();
...
Sorting and Searching ( link )