346. Moving Average from Data Stream (Array, Design, Queue, Data Stream)

링크 - https://leetcode.com/problems/moving-average-from-data-stream/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Easy

Intuition

1) Double-ended Queue

Deque를 사용하면 쉽게 풀 수 있다. deque의 사이즈를 매번 체크해서 설정한 size보다 크면 popleft를 해줘야 한다.

class MovingAverage:

    def __init__(self, size: int):
        self.size = size
        self.queue = deque()
        self.cur_sum = 0

    def next(self, val: int) -> float:
        self.queue.append(val)
        self.cur_sum += val
        if len(self.queue) > self.size:
            self.cur_sum -= self.queue.popleft()
        print(self.cur_sum)
        return self.cur_sum / len(self.queue)


# Your MovingAverage object will be instantiated and called as such:
# obj = MovingAverage(size)
# param_1 = obj.next(val)

Time Complexity: O(M) M은 next()가 call되는 개수이다.

Space Complexity: O(N) 우리는 queue에 최대 N개의 원소를 저장한다.

2) Circular Queue with Array

우리는 size만큼의 array를 0으로 초기화 시키고, 매번 가리키는 인덱스를 이동시켜 값을 구할 수 있다.

class MovingAverage:

    def __init__(self, size: int):
        self.size = size
        self.queue = [0] * size
        self.ptr = self.cur_sum = 0
        self.count = 0

    def next(self, val: int) -> float:
        self.count += 1
        self.cur_sum = self.cur_sum + val - self.queue[self.ptr]
        self.queue[self.ptr] = val
        self.ptr = (self.ptr + 1) % self.size
        return self.cur_sum / min(self.size, self.count)
        


# Your MovingAverage object will be instantiated and called as such:
# obj = MovingAverage(size)
# param_1 = obj.next(val)

Time Complexity: O(M) M은 next()가 call되는 개수이다.

Space Complexity: O(N) 우리는 queue에 최대 N개의 원소를 저장한다.