[Udemy] Sliding Window 패턴 파악하기

오늘은 배열, 문자열, 연결 리스트와 같은 선형구조에서 데이터를 입력하거나 특정 방식으로 연속적인 하위 데이터 집합을 구하는 데 용이한 Sliding Window(슬라이딩 윈도우) 패턴에 대해 알아보자.

 

문제

배열에서 n 갯수만큼 인접한 숫자들의 합 중 가장 큰 값을 반환하라.

 

input: arr = [1,2,5,2,8,1,5], n = 2

output: 10

 

input: arr = [1,2,5,2,8,1,5], n = 4

output: 17

 

input: arr = [4,2,1,6], n = 1

output: 6

 

input: arr = [4,2,1,6,2], n = 4

output: 13

 

input: arr = [], n = 4

output: null

 

일반적인 접근

function maxSubarraySum(arr,n) {
    if (arr.length < n) return null;
    
    let max = -Infinity;
     for (let i = 0; i < arr.length - n + 1; i++) {
         let temp = 0
         for (let j = 0; j < n; j++) {
             temp += arr[i+j]
         }
         max = Math.max(max, temp)
     }
    return max;
}

요소 하나를 기준으로 해당 요소 이후의 주어진 n 만큼의 요소까지의 갯수를 더해서 합을 구한다.

max와 temp(부분합)을 비교하여 최댓값을 max에 할당한다.

 

위 해결방법은 반복문이 중첩되어 있어 시간 복잡도가 O(n^2)이므로, 성능이 떨어진다.

 

Sliding Window(슬라이딩 윈도우) 패턴 접근

function maxSubarraySum(arr,n) {
    if (arr.length < n) return null;
    
    let max = 0;
    for (let i = 0; i < n; i++) {
        max += arr[i]
    }

    let temp = max;
    for (let i = n; i < arr.length; i++) {
        temp = temp - arr[i - n] + arr[i]
        max = Math.max(temp, max)
    }
    
    return max;
}

굳이 요소를 기준으로 하고 기준이 바뀔 때마자 n 만큼 길이의 부분합을 구할 필요가 없다.

처음부터 n 만큼 부분합을 구한 후 n번째 요소부터는 이미 구했던 부분합을 기반으로 첫번째 요소를 빼고 n번째 요소를 더하여 구할 수 있다.

 

위 풀이의 시간복잡도는 O(n)이므로 일반적인 접근보다 성능이 우수하다.

 

참조

Udemy - Js 알고리즘 & 자료구조 강의