[알고리즘] 문제 해결 패턴 - 기본: Slide Window

2. Slide Window

• 연속된 데이터(주로 배열이나 리스트)에서 일정한 크기의 구간(윈도우)을 움직이며 문제를 해결하는 패턴입니다. 윈도우의 크기가 고정된 경우와 가변적인 경우가 있습니다.
• 배열이나 문자열 같은 일련의 데이터를 입력하거나 특정 방식으로 연속적인 해당 데이터의 하위 집합을 찾는 경우에 유용한 패턴입니다.

 

대표적인 문제 예시

: LeetCode - Minimum Size Subarray Sum

주어진 양수로 이루어진 배열에서 연속된 부분 수열 중 원하는 합 이상을 만족하는 최소 길이의 부분 수열을 찾는 문제입니다.

 

data example 1
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2

data example 2
Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

data example 3
Input: target = 15, nums = [1,2,3,4,5]
Output: 5

 

Bad Solution : O(n^3)

function minSubarrayLenBad(target, nums) {
    let minLength = Infinity;
    for (let start = 0; start < nums.length; start++) {
        for (let end = start; end < nums.length; end++) {
            let sum = 0;
            for (let i = start; i <= end; i++) {
                sum += nums[i];
            }
            if (sum >= target) {
                minLength = Math.min(minLength, end - start + 1);
                break; // 현재 start에 대한 최소 길이 찾음
            }
        }
    }
    return minLength === Infinity ? 0 : minLength;
}

 

알고리즘 적용 : O(n)

function minSubarrayLen(target, nums) {
    let minLength = Infinity;
    let start = 0;
    let sum = 0;
    
    for (let end = 0; end < nums.length; end++) {
        sum += nums[end];
        
        while (sum >= target) {
            minLength = Math.min(minLength, end - start + 1);
            sum -= nums[start];
            start++;
        }
    }
    
    return minLength === Infinity ? 0 : minLength;
}

1. minLength 변수는 현재까지 찾은 최소 길이를 저장하는 변수로 초기에는 Infinity로 설정하여 아직 최소 길이를 찾지 못한 상태를 나타냅니다.
2. start 변수는 현재 윈도우의 시작 인덱스를 나타내며, 초기에는 0으로 설정됩니다.
3. sum 변수는 윈도우 내의 요소들의 합을 나타내는 변수입니다. 윈도우 내의 요소를 하나씩 더하면서 합을 갱신합니다.
4. 반복문에서 end 변수는 윈도우의 끝 인덱스를 나타냅니다. end가 배열의 길이보다 작은 동안 반복합니다.
5. sum에 현재 end 인덱스의 요소를 더하고 윈도우의 합을 갱신합니다.
6. 내부 while 루프는 윈도우 내의 합이 target 이상이 될 때까지 반복합니다. 이렇게 하면 최소 길이를 구할 수 있습니다.
7. minLength은 현재까지 찾은 최소 길이와 현재 윈도우의 길이 중 작은 값을 선택하여 갱신합니다.
8. sum에서 윈도우의 시작 요소를 빼고 합을 갱신합니다. 이렇게 하면 윈도우 내의 요소 합을 관리합니다.
9. 윈도우의 시작 인덱스를 오른쪽으로 이동합니다.
10. 마지막으로 최종적으로 계산된 최소 길이를 반환합니다. 만약 최소 길이가 갱신되지 않았다면 (Infinity 상태라면) 0을 반환합니다.