[알고리즘] 최대 매출 - Sliding Window

 

문제설명

현수의 아빠는 제과점을 운영합니다. 현수 아빠는 현수에게 N일 동안의 매출기록을 주고 연속된 K일 동안의 최대 매출액이 얼마인지 구하라고 했습니다.

만약 N=10이고 10일 간의 매출기록이 아래와 같습니다. 이때 K=3이면

12 15 11 20 25 10 20 19 13 15

연속된 3일간의 최대 매출액은 11+20+25=56만원입니다.

여러분이 현수를 도와주세요.

 

입력

첫 줄에 N(5<=N<=100,000)과 K(2<=K<=N)가 주어집니다.

두 번째 줄에 N개의 숫자열이 주어집니다. 각 숫자는 500이하의 음이 아닌 정수입니다.

 

출력

첫 줄에 최대 매출액을 출력합니다.

예시 입력

10 3
12 15 11 20 25 10 20 19 13 15

예시 출력

56

 

문제 풀이

N일 동안의 매출에서 매출이 가장 높은 연속된 M일의 매출을 구하는 문제이다.

 

1일차 부터 N일차 까지 순차적으로 +(M-1)일만큼 2중 for문으로 구하면 쉽게 구할 수 있다.

하지만 N에 100,000이라는 어마한 일수가 주어지게 된다면 엄청난 양의 for문을 수행하기에 굉장히 비효율적이다.

 

아래와 같은 방법으로 접근하면 효율적으로 문제를 해결할 수 있다.

sliding window

 

M을 3으로 가정하겠다. 해당 경우에서는 3일치의 합계 매출을 구하고 우측으로 한칸씩 옮겨나가면 된다.

각 단계에서 M일만큼의 합계를 구하고 각 단계에서 합계를 비교하여 최댓값을 구할 수 있다.

 

위 그림 1번단계에서 합계는 12 + 15 + 11 = 38이다. 2번단계에서는 15 + 11 + 20 = 46이다. 

알고리즘에서는 해당내용을 어떻게 구현할 수 있을까.

 

정답은 지나왔던 항목을 빼주고, 도달한 항목을 더해주면 된다.

- 1번 단계에서, 12 + 15 + 11 = 38이다.

- 2번 단계에서, 합계 38에서 지나간 12를 빼주면 38-12 = 26이 된다. 26인 상태에서 도달한 값 20을 더해주면 40이 된다.

- 해당과정을 배열의 끝까지 도달할 때 까지 반복한다.

 

int answer = 0;
int sum = 0;
        
for (int i = m; i < n; i++) {
    sum += (arr[i] - arr[i-m]);
    // 최댓값 비교
    answer = Math.max(answer, sum);
}

 

다만, for문의 시작을 m기준으로 시작하므로, m이전의 합계데이터 확인이 필요하다.

for (int i = 0; i < m; i++) {
    sum+=arr[i];
}

 

전체 소스

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        Main main = new Main();

        int n = kb.nextInt();
        int m = kb.nextInt();

        int arr[] = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }

        System.out.println(main.solution(n, m, arr));
    }

    // sliding windows 방식
    // i-m ~ i번까지 배열의 합을 구하고 오른쪽으로 배열을 한칸씩 밀며 최댓값을 구하는 방식.
    public int solution(int n, int m, int[] arr) {
        int answer = 0;
        int sum = 0;
        // 초기값 셋팅, 0번 부터 m번까지 합을 미리 구해놓는다.
        for (int i = 0; i < m; i++) {
            sum+=arr[i];
        }

        answer = sum;
        // i-m번의 값은 빼고, i번째 값을 더하면, 한칸씩 앞당기며 합을 구한 것과 같다.
        // 2중 for문보다 속도가 훨씬 빠르다.
        for (int i = m; i < n; i++) {
            sum += (arr[i] - arr[i-m]);
            // 최댓값 비교
            answer = Math.max(answer, sum);
        }
        return answer;
    }

}