최대 매출 (Sliding Window)

22 Apr 2023 in Algorithm on Java, Coding, Test

문제

설명

현수의 아빠는 제과점을 운영합니다. 현수 아빠는 현수에게 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이하의 음이 아닌 정수입니다.

출력

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

예시 입력 1

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

예시 출력 1

56

해결방법

• 슬라이딩 윈도우란 배열에서 특정 크기 만큼의 합을 구할 때 사용하는 개념

  

코드

import java.util.*;

class Main {
    public int solution(int n, int k, int[] arr) {
        int answer, sum = 0;
        // 첫 3일간 매출은 미리 계산하고 시작한다.
        for (int i = 0; i < k; i++) sum += arr[i];
        answer = sum;
        // 4일 부터 마지막 일까지 반복
        for (int i = k; i < n; i++) {
            // 1,2,3일을 계산하고 시작했으며
            // 다음 계산은 2,3,4일 매출액을 합해야 하므로
            // 4일 매출을 더하고, 2일 매출을 빼야한다
            // 이것은 4일 매출에서 2일 매출을 뺀 만큼 기존 합에 더하는 것 과 같다.
            sum += (arr[i] - arr[i - k]);
            answer = Math.max(answer, sum);
        }
        return answer;
    }

    public static void main(String[] args) {
        Main.Main T = new Main.Main();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int k = kb.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }
        System.out.print(T.solution(n, k, arr));
    }
}