[Algorithm] Sliding Window 알고리즘

문제

12 15 11 20 25 10 20 19 13 15

와 같은 N개의 원소를 가지고 있는 배열과 변수 K가 주어졌을 때 연속된 K개의 합중에서 가장 큰 값을 구해라

 

예시 입력

10 3
12 15 11 20 25 10 20 19 13 15

예시 입력의 첫번째 수는 N개의 배열을 줄것이다라는 것이고, 두번째 수는 K를 주는 것이다.

 

예시 출력

56

 

처음에 내가 짰던 알고리즘은 이중 for문을 사용하였다. 그랬더니 또 Timeout Error가 발생하였다. 나는 이중 for문을 이용해도 시간복잡도가 O(N)일거라고 생각하였다. 저 예시 입력의 경우에는,,, 생각해보면 만약 N이 100000인데, K가 60000이다? 그러면 시간복잡도는 거의 O(N*N)이 되어버린다.. 그래서 타임아웃 오류가 발생하였던 것이다.

 

하지만 Sliding Window 알고리즘을 사용하면 시간복잡도가 O(N)이 된다. 

 

일단 처음에 window에 k만큼 for문을 돌아 배열 값을 더해준다.  그 다음 window로 이동하면 이전 window와 k-1개가 겹친다. 그래서 이전 window값에서 겹치지 않는 값을 빼주고, 새로 추가된 값을 더해주면 for문을 한 번 더 돌 필요가 없어져 시간복잡도가 O(N)이 된다. 

import java.util.Scanner;

public class Section3_3_MyVer {
    private int solution(int n, int m, int[] list) {
        int answer;
        int window = 0;
        for(int i = 0; i < m; i++) {
            window += list[i];
        }
        answer = window;

        for(int j = 1; j < n-m+1; j++) {
            window += (-list[j-1] + list[j+m-1]);
            if(window > answer) {
                answer = window;
            }
        }

        return answer;
    }

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

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

        System.out.println(main.solution(n, m, list));
    }
}

저 알고리즘을 바탕으로 코드를 짰더니 Timeout Error가 발생하지 않고 통과하였다.