문제 개요
이 문제에서는 n개의 정수로 이루어진 배열과 m개의 범위 쿼리가 주어집니다. 각 쿼리가 지정하는 범위에 포함된 요소들의 평균을 구하고, 소수점 이하는 버린 정수 값을 출력하는 프로그램을 작성해야 합니다.
예시를 통해 문제를 자세히 살펴보겠습니다.
입력 −
array = {5, 7, 8, 9, 10}
m = 2; [0, 3], [2, 4]
출력 −
7 9
설명 −
- [0, 3] 범위의 요소는 5, 7, 8, 9이며, 합은 29이고 개수는 4이므로 평균은 29 ÷ 4 = 7.25 → 7
- [2, 4] 범위의 요소는 8, 9, 10이며, 합은 27이고 개수는 3이므로 평균은 27 ÷ 3 = 9.0 → 9
방법 1: 직접 순회 방식
가장 단순한 방법은 각 쿼리마다 시작 인덱스부터 끝 인덱스까지 배열을 순회하면서 요소를 모두 더한 뒤, 요소 개수로 나누는 것입니다. 이 방법은 올바른 결과를 출력하지만 한 번의 쿼리 처리에 O(n)의 시간이 걸립니다. 따라서 쿼리 개수가 많아질수록 성능이 급격히 저하되므로 효율적이지 못합니다.
방법 2: 접두사 합(Prefix Sum) 활용
더 효율적인 방법은 접두사 합 배열을 미리 계산해 두는 것입니다. 접두사 합 배열의 i번째 값은 배열의 처음부터 i번째 인덱스까지의 모든 요소의 합을 의미합니다. 예를 들어 prefixSum[4]는 인덱스 0부터 4까지의 요소 합입니다.
이렇게 준비된 prefixSum 배열을 사용하면 각 쿼리의 평균을 다음 공식으로 즉시 계산할 수 있습니다.
Mean = (prefixSum[upper] − prefixSum[lower − 1]) / (upper − lower + 1)
여기서 upper와 lower는 쿼리로 주어진 범위의 끝 인덱스와 시작 인덱스입니다. lower가 0인 경우에는 prefixSum[lower − 1]을 0으로 간주합니다.
전처리에 O(n)이 소요되지만, 이후 각 쿼리는 O(1) 만에 처리되므로 전체 시간 복잡도는 O(n + m)입니다. 쿼리마다 O(m × n)이 걸리는 직접 순회 방식과 비교하면, 쿼리가 많은 상황에서 상당한 성능 향상을 기대할 수 있습니다.
구현 예제
다음은 위 해결 방법의 동작을 보여주는 C++ 프로그램입니다.
#include <iostream>
#define MAX 100
using namespace std;
int prefixSum[MAX];
void initialisePrefixSum(int arr[], int n) {
prefixSum[0] = arr[0];
for (int i = 1; i < n; i++)
prefixSum[i] = prefixSum[i - 1] + arr[i];
}
int queryMean(int l, int r) {
int mean;
if (l == 0)
mean = (prefixSum[r] / (r + 1));
else
mean = ((prefixSum[r] - prefixSum[l - 1]) / (r - l + 1));
return mean;
}
int main() {
int arr[] = {5, 7, 8, 9, 10};
int n = sizeof(arr) / sizeof(arr[0]);
initialisePrefixSum(arr, n);
cout<<"[0, 3] 범위의 평균: "<<queryMean(0, 3)<<endl;
cout<<"[2, 4] 범위의 평균: "<<queryMean(2, 4)<<endl;
return 0;
}
출력 결과
[0, 3] 범위의 평균: 7 [2, 4] 범위의 평균: 9