[알고리즘] Sliding Window

Sliding Window 

슬라이딩 윈도우는 연속적인 리스트나 배열의 원소들의 값들을 비교하기 위한 알고리즘입니다.

 

 

예제 >

현수의 아빠는 제과점을 운영합니다. 현수 아빠는 현수에게 N일 동안의 매출기록을 주고 연속된 K일 동안의 최대 매출액이 얼마인지 구하라고 했습니다.

만약 N=10이고 10일 간의 매출기록이 아래와 같습니다. 이때 K=3이면

[2, 4, 7, 10, 8, 4, 5, 6, 7, 1]

연속된 3일간의 최대 매출액은 7+10+8=25만원입니다.

 

직관적인 방법으로 구현한다면 다음과 같이 구할 수 있습니다.

 

public class Main {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int range = scanner.nextInt();

        ArrayList<Integer> arrayList = new ArrayList<>();

        for (int i = 0; i < size; i++) {
            arrayList.add(scanner.nextInt());
        }

        int maxTotal = 0;

        for (int i = 0; i < arrayList.size() - range + 1; i++) {
            int temp = 0;
            for (int j = 0; j < range; j++) {
                temp += arrayList.get(i+j);
            }
            if (temp > maxTotal) {
                maxTotal = temp;
            }
        }
        System.out.println(maxTotal);

    }
}

 

이때 이중 포문이 돌기 때문에 시간 복잡도는 O(n^2) 이 됩니다.

그러나 중복된 부분을 삭제하고 한개의 포문으로 단순화 할 수 있습니다.

 

핵심은 매 순회마다 추가되는 인덱스와 삭제되는 인덱스가 일관성을 갖기 때문에 이를 계산하여 추가 삭제해줌으로 써 하나의 포문으로 구현가능합니다.

 

 

 public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int range = scanner.nextInt();

        ArrayList<Integer> arrayList = new ArrayList<>();

        for (int i = 0; i < size; i++) {
            arrayList.add(scanner.nextInt());
        }

        int total = 0;
        int result = 0;

        for (int i = 0; i < range; i++) {
            total += arrayList.get(i);
        }

        result = total;

        for (int i = range ; i < arrayList.size(); i++) {
            total = total + arrayList.get(i) - arrayList.get(i - range );
            result = Math.max(result , total);
        }
        System.out.println(result);
    }