자바스크립트 코딩테스트 강좌, 슬라이딩 윈도우

1. 슬라이딩 윈도우란?

슬라이딩 윈도우(Sliding Window) 기술은 주어진 배열이나 리스트에서 특정 조건을 만족하는 서브 배열(subarray) 또는 서브 문자열(substring)을 찾기 위해 사용되는 알고리즘 기법입니다. 주로 연속된 원소들이 필요한 문제에 적합하며, 문제에 따라 고정된 크기 또는 가변 크기 창(window)을 사용합니다.

1.1 슬라이딩 윈도우의 장점

슬라이딩 윈도우의 가장 큰 장점은 브루트 포스(brute force) 방법에 비해 시간 복잡도를 크게 줄일 수 있다는 점입니다. 일반적으로 O(n^2)에서 O(n)으로 줄일 수 있는 경우가 많습니다. 슬라이딩 윈도우는 두 개의 포인터를 사용하여 배열을 순회하며 효율적인 접근을 가능하게 합니다.

2. 알고리즘 문제 예시

문제: 최대 길이의 반복 문자 대체

주어진 문자열이 있을 때, ‘k’개의 다른 문자로 변경하여 만들 수 있는 가장 긴 부분 문자열의 길이를 반환하는 함수를 작성하세요.


    예시:
    입력: s = "AABABBA", k = 1
    출력: 4
    설명: 변경할 수 있는 문자는 'A' 또는 'B'이다. 'B' 두 개를 'A'로 바꿔 'AAAA'를 만들 수 있다.

문제 접근 방식

이 문제를 해결하기 위해 슬라이딩 윈도우를 사용할 수 있습니다. 여기서는 현재 윈도우에 포함된 문자의 개수를 세고, k개의 문자를 대체할 수 있는지 확인합니다.

2.1 알고리즘 단계

왼쪽 포인터(left)와 오른쪽 포인터(right)를 초기화한다.
부분 문자열의 문자를 세기 위해 HashMap을 사용한다.
현재 윈도우의 유효성을 확인한다.
유효하지 않으면 왼쪽 포인터를 이동시킨다.
현재 윈도우 크기를 기록하고, 오른쪽 포인터를 이동시킨다.
이 과정을 반복하여 최대 길이를 구한다.

3. 코드 구현

아래는 위에서 설명한 알고리즘을 바탕으로 작성한 자바스크립트 코드입니다.


    function characterReplacement(s, k) {
        const countMap = {};
        let left = 0;
        let maxLength = 0;
        let maxCount = 0;

        for (let right = 0; right < s.length; right++) {
            countMap[s[right]] = (countMap[s[right]] || 0) + 1;
            maxCount = Math.max(maxCount, countMap[s[right]]);

            while (right - left + 1 - maxCount > k) {
                countMap[s[left]]--;
                left++;
            }

            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }

    // 사용 예시
    console.log(characterReplacement("AABABBA", 1)); // 4

4. 코드 설명

위의 코드에서 우리는 ‘s’ 문자열을 주어진 ‘k’에 대해 반복적으로 처리하고 있습니다. 각 문자의 발생 빈도를 세기 위해 countMap을 사용하고 있으며, 현재 윈도우에서 가장 많이 나타나는 문자의 개수를 추적합니다.

4.1 주요 변수 설명

countMap: 각 문자의 개수를 세는 객체
left: 윈도우의 왼쪽 경계
maxLength: 최대 길이 저장
maxCount: 현 윈도우에서 가장 많이 나타나는 문자의 개수

4.2 슬라이딩 윈도우의 이동

오른쪽 포인터는 문자열의 끝까지 이동하며 증가시키고, 왼쪽 포인터는 현재 윈도우가 유효하지 않을 때만 이동합니다. 유효한 조건은 현재 윈도우의 크기에서 가장 많이 나타나는 문자의 개수를 빼고 그 결과가 ‘k’보다 작거나 같아야 합니다. 이는 특정 문자를 대체할 수 있는지를 체크하는 방식입니다.

5. 시간 복잡도와 공간 복잡도

이 알고리즘의 시간 복잡도는 O(n)입니다. 문자열의 각 문자를 한 번만 순회하며, 공간 복잡도는 O(1)입니다. 왜냐하면 알파벳 대문자만을 고려하기 때문에 단 26개의 문자를 저장할 수 있기 때문입니다.

6. 다양한 문제 해결 방법

슬라이딩 윈도우는 매우 다양하게 응용될 수 있는 기법입니다. 따라서 이 개념을 마스터 하는 것은 다른 많은 알고리즘 문제를 해결하는 데 도움이 됩니다. 예를 들어:

최대 연속 1의 개수 문제
최소 길이의 부분 수열 합 문제
모든 아나그램 찾기 문제

6.1 추가 문제 예시

다음과 같은 문제도 슬라이딩 윈도우로 효율적으로 해결할 수 있습니다:


    문제: 가장 짧은 부분 수열의 경우
    주어진 배열에서 특정 수의 합을 만들기 위한 최소의 부분 수열 길이를 찾으세요.

7. 결론

이번 강좌를 통해 슬라이딩 윈도우 기술의 기본 개념과, 이를 활용한 알고리즘 문제를 하나 풀어보았습니다. 이 기법은 특히 문자열 처리와 서브 배열 그리기 문제에서 매우 유용하므로, 충분히 연습하고 숙지하여 다양한 변형 문제를 해결할 수 있도록 하세요.

슬라이딩 윈도우 패턴을 마스터하면 알고리즘 문제의 난이도를 크게 줄일 수 있으며, 실제로 회사의 코딩 테스트에서도 자주 등장하는 주제입니다. 앞으로 많은 연습을 통해 이 기법을 완벽히 습득하시길 바랍니다.

8. 추가 리소스

더 많은 슬라이딩 윈도우 문제를 풀어보고 싶다면 LeetCode, HackerRank와 같은 온라인 플랫폼에서 수많은 문제를 찾아보실 수 있습니다.