[Algorithm] 슬라이딩 윈도우(Sliding Window) 알고리즘

슬라이딩 윈도우 알고리즘

슬라이딩 윈도우 알고리즘은 윈도우 즉 일정한 범위를 가지고 있는 것을 유지하면서 이것을 이동(sliding) 하는 것이다.

 

예를들어 2가지 긴 문자열이 주어지고 알파벳 2개만을 포함하는 가장 긴 문자열을 찾아보는 문제가 있다,

이 문제를 슬라이딩 알고리즘을 이용하여 풀면 다음과 같이 파란색으로 칠해진 영역이 윈도우가 되고 이를 하나씩 밀게 되는 것이다.

그림의 Right 를 하나씩 움직이면 되는데 Right 가 C 를 가리키면 다음 포함하는 문자열이 3개가 되므로 윈도우가 더이상 확장 되지 않고 다음 윈도우로 움직인다.

 

이런식으로 움직이게 되는 것이다. 마찬가지로 D로 움직이면 CD 만 포함하게 되는것이다.

 

Max lenght 를 값으로 가지면서 윈도우를 옮길 수 있는데 윈도우의 범위를 어떻게 기억할 것인가가 관건일 것 같다.

대표적으로는 Map 을 이용하는 방법이 있다. 위와 같은 문제에서는 

<알파벳, Index> 로 각 위치를 기억해두면 빠르게 알파벳의 시작위치를 기억할 수 있다.

Map의 size가 3이상이 되면 조건을 벗어나므로 가장 작은 인덱스를 제거하고 새로운 인덱스를 Map 에 넣으면 된다.

코드는 다음과 같다.

public int function(String s) {
    int n = s.length();
    if (n < 3) return n;
    int lIdx = 0;
    int rIdx = 0;
    Map<Character, Integer> hashMap = new HashMap<>();
    int maxx = 2;
    while (rIdx < n) {
        if (hashMap.size() < 3)
            hashMap.put(s.charAt(rIdx), rIdx++);
        if (hashMap.size() == 3) {
            int minIdx = Collections.min(hashMap.values());
            hashMap.remove(s.charAt(minIdx));
            lIdx = minIdx + 1;
        }
        maxx = Math.max(maxx, rIdx - lIdx);
    }
    return maxx;
}

 

끝!