Moving average from data stream 풀이 [슬라이딩 윈도우 기본 문제]

문제 정의

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

• window size가 주어진다.
• window size안에 들어있는 숫자들의 평균을 구해라.
• 숫자는 1개씩 들어온다.

예제 입출력

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

• [1] 의 평균: 1
• [1, 10] 의 평균: 5.5
• [1, 10, 3] 의 평균: 4.66667
• [10, 3, 5] 의 평균: 6

가장 간단한 접근법

정해진 사이즈를 초과하는 크기의 숫자가 들어오는 순간에 가장 이전에 들어왔던 숫자는 버린다.

• ex) [1, 10, 3]에서 5가 들어온다면, 1을 버린다.

풀이 코드 1

class MovingAverage {

    public LinkedList<Integer> ll = new LinkedList<>();
    public int size;

    public MovingAverage(int size) {
        this.size = size;
    }

    public double next(int val) {
        if(ll.size() == size) {
            // 이미 size만큼 채워져 있다면, 앞에꺼 빼고 뒤에 새로 넣기
            ll.removeFirst();
        }

        ll.offer(val);

        return (double) ll.stream().reduce(Integer::sum).get() / ll.size();
    }
}

직관적으로 큐를 적용할 수 있다.

• 위의 코드에서 아직 개선할 수 있는 점이 있다.
  • 모든 평균을 매번 새로 계산해줄 필요는 없다.
    • 합계를 기억해놨다가 가장 이전 숫자만 빼고, 새로 들어온 숫자만 더해주자

풀이 코드 2

class MovingAverage {

    public int[] circularQueue;
    public int count;
    public int sum;

    public MovingAverage(int size) {
        this.circularQueue = new int[size];
        this.count = 0;
        this.sum = 0;
    }

    public double next(int val) {
        int pointer = count % circularQueue.length;

        if(count >= circularQueue.length) {
            sum -= circularQueue[pointer];
        }

        sum += val;
        circularQueue[pointer] = val;

        count += 1;

        return (double) sum / Math.min(count, circularQueue.length);
    }
}

• 성능 최적화를 더 극대화 하기 위해 큐 객체도 사용하지 않았다.
• size 크기의 배열만 있으면 pointer를 이용해 원형 큐처럼 사용할 수 있다.
• size 를 초과하여 숫자가 들어올 때마다, 처음에 존재하던 숫자를 빼주자.
  • 더하는 건 원래 들어올 때마다 더했으니까 똑같다.
• 시간복잡도가 O(N)에서 O(1)이 된다.

정리

• 큐를 이용해 직관적으로 풀 수 있음.
  • 사실 숫자 하나 바뀌는데, 매번 모든 인덱스를 순회하는건 비효율
  • 계산했던 값을 기억하는 방식으로 조금 더 효율적으로 문제를 풀 수 있음