Leetcode - 346. Moving Average from Data Stream

문제

입력이 아래와같이 주어진다. 이동평균(moving average) 크기가 주어지고, 값이 계속 추가될때 마다 moving average 크기만큼의 평균을 구하라.

Input
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
Output
[null, 1.0, 5.5, 4.66667, 6.0]

Explanation
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // return 1.0 = 1 / 1
movingAverage.next(10); // return 5.5 = (1 + 10) / 2
movingAverage.next(3); // return 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // return 6.0 = (10 + 3 + 5) / 3

https://leetcode.com/problems/moving-average-from-data-stream/

해결 O(1) / O(N)

구간합을 활용해 매번 size 만큼 더해서 평균을 내지 않고 O(1)만에 계산. next함수의 최대 호출 갯수인 10001개만큼의 배열을 할당해야했다.

#define DATA_SIZE 10001

typedef struct {
    int cur_size;
    int size;
    int idx;
    int total;
    int *data;
} MovingAverage;

MovingAverage* movingAverageCreate(int size) {
    MovingAverage *obj = malloc(sizeof(MovingAverage));
    obj->total = 0;
    obj->size = size;
    obj->cur_size = 0;
    obj->idx = 0;
    obj->data = (int *)calloc(DATA_SIZE, sizeof(int));
    return obj;
}

double movingAverageNext(MovingAverage* obj, int val) {
    int sum = 0;
    if (obj->cur_size < obj->size)
        obj->cur_size++;
    obj->data[obj->idx] = val;       
   
    if (obj->idx - obj->size < 0)
        sum += obj->total + obj->data[obj->idx];
    else
        sum += obj->total - obj->data[obj->idx - obj->size] + obj->data[obj->idx];
    obj->total = sum;
    obj->idx++;
        
    return (double)sum / obj->cur_size;
}

void movingAverageFree(MovingAverage* obj) {
    free(obj->data);    
    free(obj);    
}