[알고리즘] 슬라이딩 윈도우

1. 슬라이딩 윈도우 알고리즘

창문을 왼쪽부터 오른쪽으로 밀어오면서 창문안에 있는 값들을 부분배열로 조건에 맞는 경우를 찾는 알고리즘.

문자열에서 어떤 조건을 찾을때 완전탐색기법을 이용하면 이중포문을 사용하면 되는데 최악의 경우 O(n2)의 시간복잡도를 가지는데, 슬라이딩 윈도우 알고리즘을 사용할 경우 O(n)만큼 시간을 단축할 수 있다.

 

슬라이딩 윈도우는 고정된 일정한 사이즈로 앞부분과 뒷부분만 변경해주는 기법이다. 이는 구간이 일정하기 때문에 시작점을 알면 끝점을 알수 있어서 투포인터와 달리 굳이 2개가 필요하지 않다. 예를 들어 길이가 4라고 고정되었을 때 다음과 같이 구간을 탐색하게 된다.

• start = 0, 🟦🟦🟦🟦⬜️⬜️⬜️
• start = 1, ⬜️🟦🟦🟦🟦⬜️⬜️
• start = 2, ⬜️⬜️🟦🟦🟦🟦⬜️
• ...

예제 문제)

백준 1593번: 문자 해독

package com.company;

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

public class CharDecode {
    public static void main(String[] args) {
        int wlen,slen;
        String w, s;
        int[] wArr = new int[52];
        int[] sArr = new int[52];

        Scanner scan = new Scanner(System.in);
        System.out.print("문자열 길이?");
        wlen = Integer.parseInt(scan.next());
        slen = Integer.parseInt(scan.next());

        //버퍼 초기화
        scan.nextLine();
        System.out.print("W문자?");
        w = scan.nextLine();

        System.out.print("S문자?");
        s = scan.nextLine();

        //wArr 배열 셋팅
        for(char c: w.toCharArray()){
            putWord(c, wArr, 1);
        }

        int start=0;
        int cnt=0;
        int size=0;

        for(int i=0;i<s.length();i++){
            char sc = s.charAt(i);
            putWord(sc,sArr,1);
            size++;

            if(size==w.length()){
                if(Arrays.equals(wArr, sArr)){
                    cnt++;
                }
                putWord(s.charAt(start), sArr, -1);
                start++;
                size--;
            }
        }
        System.out.println(cnt);
    }

    static void putWord(char word, int[] arr, int dif){
        //'A'는 아스키코드값 65, 'a'는 97
        if('a'<= word && word<='z'){
            arr[word-'a']+=dif;
        }else{
            arr[word-'A'+26]+=dif;
        }
    }
}