[Java] sliding windows

정의

슬라이딩 윈도우(Sliding Window) 알고리즘은 배열이나 리스트의 요소의 일정 범위의 값을 비교할때 사용하면 유용한 알고리즘이다.

문제

현수의 아빠는 제과점을 운영합니다. 현수 아빠는 현수에게 N일 동안의 매출기록을 주고 연속된 K일 동안의 최대 매출액이 얼마인지 구하라고 했습니다.
만약 N=10이고 10일 간의 매출기록이 아래와 같습니다. 이때 K=3이면
12 1511 20 2510 20 19 13 15
연속된 3일간의 최대 매출액은 11+20+25=56만원입니다.

풀이

연속된 배열 원소를 더한 값 중에서 가장 큰 값을 구해야 하기 때문에 배열의 0부터 k까지의 합을 더해서 미리 저장해준다.
이후 배열을 k부터 for문을 돌리면서 배열의 i값은 더해주고 i-k값은 빼준다.
왜냐하면 한칸씩 이동하면서 가장 큰 값을 구해야 하기 때문이다.

코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

class Main {

    public int solution(int n, int k, int[] a) {

        int answer = 0;
        int sum = 0;

        for (int i = 0; i < k; i++) {
            sum += a[i];
        }
        answer = sum;

        for (int i = k; i < n; i++) {
            sum += (a[i] - a[i - k]);
            answer = Math.max(answer, sum);
        }

        return answer;
    }

    public static void main(String[] args) {
        Main solution = new Main();
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

        System.out.println(solution.solution(n, k, a));

        /*int m = scanner.nextInt();
        int[] b = new int[m];
        for (int i = 0; i < m; i++) {
            b[i] = scanner.nextInt();
        }*/

        /*for (int x : solution.solution(n, m, a, b)) {
            System.out.print(x + " ");
        }*/
    }
}