N개의 측정치가 주어질 때 M개의 이동 평균을 계산하라.(2)

package kwo2002.java;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by kwo2002 on 2015-08-21.
 */
public class MAverage {
    public List<Double> mAvg(List<Integer> nList, int m) {
        if (m > nList.size()) {
            throw new IllegalArgumentException();
        }

        List<Double> avgList = new ArrayList<>();

        double firstSum = 0.0d;

        for (int i = 0; i < m; i++) {
            firstSum += nList.get(i);
        }

        avgList.add(firstSum / m);

        int minusCnt = 0;
        for (int i = m; i < nList.size(); i++) {
            firstSum -= nList.get(minusCnt);
            firstSum += nList.get(i);

            avgList.add(firstSum / m);
            minusCnt++;
        }


        return avgList;
    }

    public static void main(String[] args) {
        MAverage mAverage = new MAverage();
        System.out.println(mAverage.mAvg(Arrays.asList(59, 54, 70, 60, 50, 55), 3));

    }

}

회고.

알고리즘 문재해결 6단계를 인지하고 2단계를 작성해봄.

알고리짐 문제해결 6단계.

1. 문제를 읽고 이해한다.

2. 문제를 익숙한 용어로 재정의한다.

3. 어떻게 해결할지 계획을 세운다.

4. 계획을 검증한다.

5. 프로그램으로 구현한다.

6. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.

2단계 작성내용.

각 위치에서 지난 M개의 합을 구하고 M으로 나누면 됨.

얼핏 보기에 진짜 별거 아니지만, 확실히 이렇게 문제를 프로그래밍적으로 재정의 해서 적으니 생각하기가 훨씬 수월해졌음!!

측정치가 고작 3이라면,

매번 각위치에서 지난 3개의 합을구하고 3으로 나눠서 평균을 구하면 첫번째 풀었던 방식으로도 문제될게 없지만, 

측정치가 10만이라면 이야기가 달라진다.

매번 각위치에서 지난 10만개의 합을 구하고 평균을 낸다고 하면 너무 비효율적이다.

왜냐하면 각위치의 합은 첫번째 값과 M번째값만 다르고 나머지는 모조리 중복이다.

첫 M의 평균은 전체의 합을 구해서 M으로 나눠서 구하고,

두번째 M의 평균은 첫 M의 합의 첫번째 값을 빼고, M+1의 값을 더해줌으로써 중복을 제거하고 효율적으로 계산할 수 있다.