[알고리즘] Sliding Window

특정 배열에 대해 범위 단위로 로직을 처리할 때 주로 사용되는 알고리즘이다.

pointer가 두개라는 점에서 Two-Pointers 알고리즘과 유사하지만, Two-Pointers알고리즘이 서로 독립적으로 움직이는 것과 달리 Sliding window 알고리즘은 포인터 두 개가 서로 동일하게 움직인다.

사실 내 생각에 두 알고리즘을 구분하는 것은 의미가 없어 보인다.

전체 element에 대해 Loop를 돌아야할 문제를, 포인터를 두 개 두고 element 하나씩 찍어가면서 돌면 two pointer고, range 단위로 비교하게 되면 sliding window라고 생각한다.

 

예컨데 대상배열(전체배열)과 비교 target인 기준배열이 있다면, left와 right라는 pointer 두 개를 두고, 순회가 끝나면  두 개의 pointer를 일괄적으로 한번에 늘려주도록 처리한다.

 

이렇게 기준배열의 크기를 고정한 채 옮기면서 범위내의 로직 처리를 행할 수 있다.

 

 

예시1 - 567. Permutation in String

 

leetcode의 가장 단순한 sliding window를 사용해서 풀 수 있는 예시문제인 567번을 보자

s1, s2라는 두 개의 string이 들어왔을 때, s2에 s1으로만 이루어진 부분이 있는지 여부를 리턴하는 문제이다.

이 문제는 s1만큼의 길이를 연쇄적으로 s2의 부분부분과 비교하는 문제이므로 sliding window를 적용할 수 있다.

 

단순하게 생각해낼 수 있는 풀이는 다음과 같다.

경계값을 걸러내준 뒤, left와 right 포인터를 두고, s2를 쪼개 sort한 후, pointer를 옮겨가면서 비교하는 것이다.

그러나 이러한 방법은 매 순회마다 대상이 되는 부분을 쪼갯다 붙여야 하므로 time limit이 걸린다.

 

효율적인 비교를 위해 Map을 사용할것이다. freq라는 맵을 만들고 잘라낸 범위 안의 원소 및 해당원소의 갯수만 비교하는 것이다. 기본적으로 anagram이기 때문에 해당 구간에서 사용한 원소와 그 빈도만 알면 되기 때문이다. 

 

s1에 Loop를 돌려서 각 원소별 사용빈도를 map에 기록한다.

예시의 경우 "ab","eidbaooo"를 input으로 받으므로 위과 같이 map이 생성된다.

 

실제 로직은 다음과 같이 반복문이 된다.

end 위치가 전체 길이보다 짧거나 같을때까지 loop를 돈다

위와 같이 input을 받았다고 해보자

start와 end는 초깃값 0으로 각각 startletter, endletter 라는 포인터를 만들것인데, 이 포인터가 바뀌는 조건은 세가지가 있다.

 

1) endletter가 freq에 있는 경우 -> 해당 endletter의 freq값을 1 줄인다

1-1) end와 start사이의 길이가 index 길이와 같다면 true를 리턴한다

2) endletter는 없지만 startletter가 freq에 있는 경우 -> start letter를 1칸 우측으로 옮긴다

3) 모두 없는 경우 -> end와 start를 모두 1칸 우측으로 옮긴다

 

순서대로 그려보면 다음과 같다

즉, 조건1은 해당 letter가 있을 경우 freq에서 지수를 줄이는 역할을

조건2는 해당 letter가 없을 경우 freq에서 줄였던 지수를 다시 늘리는 역할을 한다.

조건3은 둘 다 해당하지 않는 경우 start와 end를 모두 옮기는 역할을 한다.

 

이렇게 false인 경우에 대해서도 테스트해보자

 

그림처럼 a,b까지는 조건에 부합하므로 freq를 하나씩 줄이다가

w를 만났을때는 조건과 어긋나므로 start를 옮기며 줄였던 freq를 다시 복원시켜준다

이때 조건1은 0이 아닌 경우로 한정주어야 하는데, 그 이유는 'abc', 'aaabc'와 같은 케이스에서 a의 freq가 마이너스가 될 수도 있기 때문이다.

 

풀이의 핵심을 요약하자면 다음과 같다

 

1) Map객체로 기준을 만들어준다

2) pointer를 두 개 생성하여 Loop를 돌며 기준을 변경한다 <--- sliding window

3) 기준에 따른 리턴 조건을 만들어 준다. 이때 answer는 indexLength를 만족해야 한다

 

 

비슷한 예시의 문제를 하나 더 풀어보자

 

 

 

예시2 - 438. Find All Anagrams in a String

 

input은 동일한데 조건을 만족하는 subset이 여러개 있을 수 있고, 해당 subset이 시작하는 letter의 위치를 리턴하라는 문제이다

 

아주 유사한 문제다

다만 567번과 다르게 result라는 배열을 만들어 조건을 만족하는 인덱스를 담아 리턴해야된다는 부분만 다르다.