문제
연속된
w개 값의 평균(정수 나눗셈)들 중 최댓값과 최솟값의 차이를 구한다.
풀이
길이 w의 슬라이딩 윈도우 합을 유지하며 이동 평균을 모두 기록한 후, 최댓값과 최솟값의 차를 출력한다. 합 갱신은 이전 값을 빼고 새 값을 더하는 O(1)이다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int num_datasets;
if (!(cin >> num_datasets)) return 0;
for (int t = 1; t <= num_datasets; t++) {
int n, w;
if (!(cin >> n >> w)) break;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<int> averages;
long long current_sum = 0;
for (int i = 0; i < w; i++) {
current_sum += a[i];
}
averages.push_back(current_sum / w);
for (int i = w; i < n; i++) {
current_sum += a[i] - a[i - w];
averages.push_back(current_sum / w);
}
int max_val = *max_element(averages.begin(), averages.end());
int min_val = *min_element(averages.begin(), averages.end());
cout << "Data Set " << t << ":" << endl;
cout << max_val - min_val << endl << endl;
}
return 0;
}복잡도
- 시간: O(n)
- 공간: O(n)