슬라이딩 윈도우 - Leetcode 03

문제

주어진 문자열에서 문자의 중복을 허용하지 않는 연속된 부분 문자열 중 가장 긴 길이를 구해라.

 

해결 과정

0 <= s.length <= 5 * 10^4

 

문자열 길이의 범위를 확인했을 때 브루트 포스 방식이 원하는 해결 방식은 아니라는 결론이 나온다. 하지만 적어도 문자열의 각 문자들을 한 번씩은 살펴봐야 할 테니 O(n)의 방식이 있는지 생각해 봐야 한다.

 

아이디어를 얻기 위해 문제에서 얻을 수 있는 단서는 다음과 같다.

연속된 부분 문자열

부분 문자열이 서로 떨어져도 되는 경우라면 문제 해결 방법이 더욱 까다로워 지겠지만 연속된 부분 문자열이다. 연속된 부분 문자열(윈도우)을 관리(슬라이딩)하면서 최장 부분 문자열의 길이를 찾아내면 된다.

 

`abcabcbb` 를 예시로 생각해보자. 앞에서부터 문자 하나씩 반복하여 살펴보자.

a는 그 자체로 합리적이다. ab 역시 합리적, abc까지 합리적이다. abca에 온 순간 a는 두 번 등장하여 윈도우에 변화를 줘야 한다. 변화를 주기 전에 이전 윈도우의 길이를 최장 길이로 업데이트한다. 이제 앞의 a를 제거하고 현재 윈도우를 bca로 옮길 것이다. bcab로 가니 또 b가 두 번 등장하여 cab로 윈도우를 옮긴다. 해당 내용을 반복하다 보면 정답은 3이 된다. 알고리즘을 요약하면 다음과 같다.

1. 0번째 문자부터 반복하여 탐색해 나간다.
2. 중복되는 문자가 없다면 계속해서 윈도우에 추가하고 탐색해 나간다.
3. 중복되는 문자가 발생 했다면 일단 최장 길이를 업데이트한 후에, 중복된 문자가 최초로 나타날 때까지 윈도우의 앞에서부터 문자를 제거한다.
4. 반복문의 반복이 끝나면 답을 반환한다.

 

이 알고리즘을 코드로 구현하면 된다. 구현에 대한 아이디어는 간단하다.

• 반복 탐색 -> 반복문
• 중복되는 문자 확인 -> Set 자료구조
• 최장 길이 업데이트 -> Math.max

 

코드를 첨부하진 않겠다. 볼 때마다 해당 내용을 구현하여 슬라이딩 알고리즘에 대해 느껴보면 좋겠다. 주의할 점은 문자열의 길이가 0인 경우도 발생한다는 것이다. leet code는 친절하지만, hidden case에 존재하여 감점될 수도 있으니 주의하자.

 

슬라이딩 윈도우

순회하면서 그 '부분'에 대한 처리를 할 때, 브루트 포스로 해결하기에는 너무 효율적이지 못하고, 최소 한 번의 반복은 필요한 O(n)의 해결방안을 떠올려야 할 것 같을 때에 보통 스택, 큐 자료구조를 활용하거나 슬라이딩 윈도우, 투포인터라고 명칭 하는 알고리즘들로 접근하게 된다.

슬라이딩 윈도우는 투포인터의 특별한 일종이고, 연속된 부분을 일정한 방향으로 이동해 나가면서 답을 찾아 나가는 처리 기법이다. 반복문 한 번으로 처리 가능하니 시간 복잡도는 O(n)으로 판별할 수 있다.

 

슬라이딩 윈도우가 아닌 투포인터

 

두 개의 index 포인터로 답을 추론해 나가는 알고리즘이 투포인터 알고리즘이다. 슬라이딩 윈도우는 두 개의 포인터가 같은 방향으로 움직이지만 일반적으로 알고 있는 투포인터 알고리즘은 보통 양 끝에서 포인터가 서로 다른 방향으로 움직이게 된다. 또 투포인터는 요소 간의 관계나 조건을 확인하고 연속되지 않은 요소들도 다룰 수 있다. 다음에 다루겠지만 두 수의 합이 target과 같은 쌍을 찾는 문제가 대표적인 투포인터 문제이다. (물론 nlogn의 비용을 지불하고 배열을 정렬시켜야 포인터 이동 로직이 명확해진다.)

 

깨달음의 팁

연속된 부분 문자열에 대해 무언가를 처리하면 될 때, O(n)이 최선일 것 같을 때 접근해 보면 좋다. 특히 문제 상황에서 주어진 간단한 예제에 대한 답을 구하는 과정을 통해서 내 뇌가 어떤 과정으로 답을 구했는지 접근해 보면 그게 슬라이딩 윈도우와 연결될 때가 많은 것 같다.