[슬라이딩윈도우] 최대 매출

자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다.

 

 

 

 

📋 문제

가게를 운영하는 현수 아빠는 현수에게 N일 간의 매출 기록을 주고 연속된 K일 간의 최대 매출액이 얼마인지 구하라고 했다.

N개의 매출액이 주어졌을 때 연속된 K일 간의 최대 매출액을 구해 출력한다.

만약 10일간의 매출 기록이 12 15 11 20 25 10 20 19 13 15 로 주어졌고 K=3이라면 연속된 3일 간의 최대 매출액은 11 + 20 + 25 = 56 만원이다.

 

 

👉 입력

첫 번째 줄에 N과 K가 주어진다.

N은 5 이상의 수를 가지며 K는 2 이상 N 이하의 수를 가진다.

두 번째 줄에 N개의 숫자가 주어진다.

이때 각 숫자는 0 이상, 500 이하의 정수이다. 

 

 

👈 출력

연속된 K일 간의 최대 매출액을 출력한다.

 

 

💡 사용된 개념

Sliding Window

길이가 n인 배열이 주어지고 이 배열을 순회하며 연속적으로 같은 개수의 요소를 참조할 때 쓰면 유용한 알고리즘이다.

 

위 문제의 예시처럼 10개의 요소가 주어지고 길이가 3인 연속 부분 수열을 참조한다고 할 때 그림과 같이 참조할 수 있다.

고정된 사이즈의 윈도우가 배열을 순회하는 것이 마치 슬라이딩 하는 것과 같아 Sliding Window 알고리즘이라는 이름이 붙은 것 같다.

 

 

📝 풀이

 

Two pointers

 

function solution(k, arr) {
    let answer = [];
    let sum = 0;
    let start = 0;

    for (let end = k - 1; end < arr.length; end = start + k - 1) {
        sum = 0;
        for (let i = start; i <= end; i++) {
            sum += arr[i];
        }
        start++;
        answer.push(sum);
    }

    return Math.max(...answer);
}

let a = [12, 15, 11, 20, 25, 10, 20, 19, 13, 15];
console.log(solution(3, a));

 

처음에는 투 포인터 알고리즘을 이용해 문제를 풀었다.

3일 간의 매출액을 참조해야 하기 때문에 start와 end는 2만큼 떨어져 있어야 한다.

 

따라서 start를 0으로 초기화했을 때 end는 k - 1(=2)부터 시작해 주어진 배열 arr의 길이만큼 배열을 순회한다.

이때 start가 1씩 증가하면 end는 start + k - 1 만큼 증가해야 한다.

 

이 배열을 순회하며 start에서 end만큼의 부분 합을 구해 sum을 저장하고 배열 answer에 삽입한다.

sum을 구하는 작업이 끝났다면 start와 end를 옮겨 새로운 연속 부분 수열을 탐색한다.

 

주어진 배열의 순회가 끝났다면 answer에는 연속된 3일 간의 매출액들이 담긴다.

따라서 전개연산자를 이용해 이 중 최댓값을 골라낸다.

 

하지만 위와 같이 풀면 이중 for문이 있기 때문에 시간복잡도가 O(n^2)이 될 것이다.

그러므로 이 문제에서는 3일이라는 고정된 윈도우를 사용할 수 있으므로 Sliding Window 알고리즘을 사용하는 것이 시간복잡도 면에서 훨씬 낫다.

 

 

Sliding Window

 

function solution(k, arr) {
    let answer = 0, sum = 0;

    for (let i = 0; i < k; i++) sum += arr[i];
    answer = sum;

    for (let i = k; i < arr.length; i++) {
        sum += (arr[i] - arr[i - k]);
        answer = Math.max(answer, sum);
    }

    return answer;
}

let a = [12, 15, 11, 20, 25, 10, 20, 19, 13, 15];
console.log(solution(3, a));

 

answer는 최댓값을 저장할 변수이고 sum은 연속 부분 수열의 합을 저장할 변수이다.

먼저 주어진 배열 arr의 첫 번째 인덱스부터 K까지의 부분합을 구해 sum에 저장한다.

이때 sum은 12 + 15 + 11의 값이 담기고 이를 다음의 부분합과 비교하기 위해 answer에 저장한다.

 

이미 K 까지 부분합을 구했기 때문에 두 번째 for문은 K 부터 arr의 길이만큼 돈다.

이때 슬라이딩을 하듯이 새로운 값을 sum에 더하면 sum에서 이전에 참조한 연속 부분 수열의 첫 번째 값을 뺀다.

 

 

이 사진에서 12, 15, 11을 참조하던 윈도우가 15, 11, 20으로 넘어갈 때 sum은 20을 더하고 12를 빼는 것이다.

 

이후 answer에 저장된 기존의 최댓값과 현재 연속 부분 수열의 부분합 중 최댓값을 선택해 answer의 값을 갱신해 나간다.

이로써 for문의 순회가 끝났다면 answer에는 연속 부분 수열의 합 중 최댓값이 남게 된다.