3-3 최대 매출 (Java)

✏️ 문제

---

설명

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

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

12 1511 20 2510 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

---

✏️ 코드

import java.util.Scanner;

class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        for (int i=0; i<n; i++) {
            arr[i] = sc.nextInt();
        }

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

    public static int solution(int n, int k, int[] arr) {
        int maxSum = 0;
        int answer = 0;
        for (int i=0; i<k; i++) {
            maxSum += arr[i];
        }
        answer = maxSum;
        
        for (int i=k; i<n; i++) {
            maxSum += (arr[i]-arr[i-k]);
            answer = Math.max(answer,maxSum);
        }

        return answer;
    }
}

K=3 (즉 3개 연속이다) 일떄의 최대합을 구해야한다.
역시 이중for문으로 풀 수 있지만 시간 복잡도면에서 효율적이지 못한다.

배열의 크기와 구간이 정해져있기 때문에 슬라이딩 윈도우 알고리즘으로 문제를 풀어나가면 된다.

우선 배열의 첫번쨰부터 3개까지의 합을 구해 놓는다.

그 다음 3개의 합은 첫 3개의 합에서 그 다음 인덱스의 값을 더하고 첫번째 인덱스 값을 뺴주면 된다.
i=k(i=3) 부터 돌기 떄문에 처음 합인 maxSum에 arr[3]값을 더하고 arr[i-k](arr[0]을 빼주면 다음 3개의 값이 된다

그 이후도 계속 3개의 원소 중 첫번쨰 값을 빼면서 3칸씩 합을 구해준다.

마지막으로 구해준 값을 항상 최대값과 비교하여 더 큰 값이 있을 경우 더 큰 값에 넣어주면서 비교하면 된다.

---

정리

슬라이딩 윈도우 알고리즘