슬라이딩 윈도우

언제 쓰나

배열이나 문자열에서 연속된 구간 하나를 골라야 하고, 그 구간이 조건을 만족하는지 앞에서부터 이어서 판단할 수 있을 때 씁니다.

• “중복 문자가 없는 가장 긴 부분 문자열”, “합이 target 이상인 가장 짧은 부분 배열”처럼 조건을 지키는 가장 긴 구간이나 가장 짧은 구간을 찾습니다.
• “길이가 k인 구간 중 합이 가장 큰 것”처럼 길이가 정해진 구간을 한 칸씩 옮겨 가며 봅니다.
• 구간을 늘리면 조건이 깨지고, 앞을 줄이면 다시 지켜지는 성질이 있습니다. 이 성질이 있어야 왼쪽 끝을 뒤로 되돌리지 않고 앞으로만 옮길 수 있습니다.

어떻게 동작하나

모든 구간을 보면 같은 칸을 여러 번 읽는다

LeetCode 3은 문자열 s에서 같은 문자가 두 번 나오지 않는 가장 긴 연속 부분 문자열의 길이를 구하는 문제입니다. s = "abcabcbb"이면 "abc"가 가장 길어서 답은 3입니다.

가장 먼저 떠오르는 방법은 시작 칸을 하나씩 정하고, 거기서부터 중복이 나올 때까지 늘려 보는 것입니다.

1. 0번 칸에서 시작하면 "a", "ab", "abc"까지 괜찮고, "abca"에서 'a'가 겹칩니다. 길이 3입니다.
2. 1번 칸에서 시작하면 "b", "bc", "bca"까지 괜찮고, "bcab"에서 'b'가 겹칩니다.
3. 2번 칸, 3번 칸에서도 같은 식으로 다시 늘려 봅니다.

2번 과정에서 확인한 "bc"는 1번 과정의 "abc" 안에 이미 들어 있던 문자열입니다. "abc"에 중복이 없었으니 그 안의 "bc"에도 중복이 없다는 것을 알고 있는데도, 시작 칸을 옮길 때마다 처음부터 다시 셉니다. 길이가 n인 문자열이면 시작 칸이 n개이고 칸마다 최대 n칸을 늘려 보므로 O(n²)입니다.

앞을 버리고 뒤를 이어 붙인다

다시 세지 않으려면 "abca"에서 겹쳤을 때 처음부터 새로 시작하지 않고, 겹친 원인만 앞에서 덜어내면 됩니다. "abc" 뒤에 'a'를 붙이려는 순간을 그려 보면 다음과 같습니다.

창 · s = "abcabcbb"

테두리 안에 'a'가 이미 있으니 테두리의 왼쪽 끝에서 'a'를 뺍니다. 그러면 구간은 "bc"가 되고, 여기에 새 'a'를 붙인 "bca"는 다시 중복이 없습니다. "bc"에 중복이 없다는 것은 이미 알고 있으니 다시 확인하지 않습니다.

이렇게 연속 구간의 양 끝을 두 변수로 기억하고, 오른쪽 끝을 한 칸씩 늘리다가 조건이 깨지면 왼쪽 끝을 줄여 가며 배열을 한 번만 훑는 방법을 슬라이딩 윈도우(sliding window)라고 부릅니다. 테두리가 창(window)처럼 문자열 위를 미끄러지며(sliding) 오른쪽으로 옮겨 가서 붙은 이름입니다. 코드에서는 네 가지 값을 기억합니다.

• left: 창의 왼쪽 끝 칸입니다. 줄일 때 한 칸씩 오른쪽으로 갑니다.
• right: 창에 넣을 오른쪽 끝 칸입니다. 반복 한 번마다 한 칸씩 오른쪽으로 갑니다.
• seen: 창 안에 있는 문자를 담은 Set입니다. 새 문자가 창 안에 있는지 O(1)에 확인합니다.
• best: 지금까지 본 창 가운데 가장 긴 창의 길이입니다. 마지막에 이 값을 돌려줍니다.

right 칸의 문자를 넣을 때 할 일은 두 가지입니다.

1. 창 안에 같은 문자가 있으면 left 칸의 문자를 seen에서 빼고 left를 한 칸 옮깁니다. 같은 문자가 빠질 때까지 반복합니다.
2. 이제 같은 문자가 없으니 right 칸의 문자를 seen에 넣고, 창의 길이 right - left + 1로 best를 갱신합니다.

1번에서 창을 줄일 때 겹친 문자 하나만 빼지 않고 그 앞의 문자까지 모두 빼는 이유는 창이 연속 구간이어야 하기 때문입니다. "cab"에 'b'를 넣을 때 'b'만 빼면 "ca"와 새 'b' 사이가 벌어져 연속 부분 문자열이 아니게 됩니다.

직접 따라가 보기

아래에서 “다음”을 누르면 right가 한 칸씩 들어오며 파란 창이 늘어나고, 겹치는 문자가 나오면 왼쪽 칸이 빨갛게 빠지며 창이 줄어듭니다. 4번째 단계에서 창이 "abc"까지 늘어 best가 3이 되고, 5번째 단계에서 right가 두 번째 'a'에 닿으면 첫 'a'가 빠집니다. 11번째 단계에서는 'b' 하나를 넣으려고 'a'와 'b' 두 칸을 한꺼번에 뺍니다. 변수 칸의 moves는 left와 right가 움직인 횟수의 합인데, 끝까지 넘겨도 16(2n)을 넘지 않는 것을 보세요.

처음부터 이전 자동 재생 다음

단계 1 / 15

슬라이딩 윈도우 · s = "abcabcbb"

변수

left

0

right

0

seen

Set {}

moves

0left·right 이동 합, 최대 2n = 16

best

0

left와 right 모두 0번 칸에서 시작합니다. 창은 아직 비어 있습니다. "다음"을 눌러 보세요

• right가 방금 넣은 칸
• 창 안의 칸
• left가 지나간 칸
• 가장 길었던 창 (best)

대표 문제 풀이

아래는 참고 풀이입니다. 주석의 ①②가 위의 두 규칙과 같은 순서이고, 변수 이름은 시각화의 변수 칸과 같습니다.

function lengthOfLongestSubstring(s) {
  const seen = new Set();
  let left = 0;
  let best = 0;

  for (let right = 0; right < s.length; right++) {
    // ① 창 안에 같은 문자가 있으면, 그 문자가 빠질 때까지 왼쪽에서 줄인다
    while (seen.has(s[right])) {
      seen.delete(s[left]);
      left++;
    }
    // ② 오른쪽 끝을 넣고 창 길이로 best를 갱신한다
    seen.add(s[right]);
    best = Math.max(best, right - left + 1);
  }

  return best;
}

for 안에 while이 있어 두 겹 반복처럼 보이지만, 시간은 O(n)입니다. while이 한 번 돌 때마다 left가 한 칸 오른쪽으로 가는데, left는 뒤로 돌아가지 않고 right를 앞지르지도 않으니 전체 실행을 통틀어 최대 n번만 움직입니다. right도 n번 움직이므로 두 반복문이 실행되는 횟수의 합은 2n을 넘지 않습니다. 공간은 seen에 든 문자 수만큼이고, 창 안의 문자는 서로 다르므로 문자열 길이 n과 문자 종류 수 m 가운데 작은 쪽을 넘지 않습니다.

자주 하는 실수

반복문이 두 겹이라 O(n²)로 계산합니다. 저는 처음에 “left도 n만큼, right도 n만큼 움직이는데 while이 두 개이니 O(n²)“라고 답했습니다. 두 겹 반복을 O(n²)로 보는 것은 바깥 반복 한 번마다 안쪽이 최대 n번 돈다고 곱한 계산입니다. 여기서는 안쪽 while이 left를 옮기는 횟수가 바깥 반복 한 번마다가 아니라 전체를 통틀어 n번으로 제한됩니다. 곱하지 않고 더해야 하고, 그래서 n + n = 2n입니다.

첫 문자를 반복문 밖에서 따로 넣습니다. 저는 첫 문자를 반복문 앞에서 seen에 넣고 반복문을 right = 1부터 시작했는데, best 갱신은 반복문 안에만 있었습니다. 그러자 s = "a"에서는 반복문이 한 번도 돌지 않아 1이 아니라 0이 나왔습니다. 위 풀이처럼 right = 0부터 같은 반복문에서 넣고 갱신하면 빈 문자열과 한 글자 문자열도 따로 처리하지 않아도 됩니다.