[Algorithm] 최대 매출

최대 매출

설명

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

출력

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

예시 입력 1

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

예시 출력 1

56

---

해결

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public int solution(int n, int k, int[] arr) {
        int answer = 0;
        int sum = 0;
        // arr배열의 (k-1)번 요소까지 합을 구함
        for (int i=0; i<k; i++) sum += arr[i];
        answer = sum;

        // 배열의 k번부터 순회하며 순차대로 k개의 합을 구하고 최대값을 도출한다
        for (int i=k; i<n; i++) {
            // 배열의 인덱스를 하나씩 밀어가면서 sum을 구함
            sum += (arr[i]-arr[i-k]);
            answer = Math.max(answer, sum);
        }

        return answer;
    }

    public static void main(String[] args) throws IOException {
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i=0; st.hasMoreTokens(); i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        System.out.println(T.solution(N, K, arr));
    }
}

• 슬라이딩 윈도우 알고리즘으로 문제를 풀었다.
• 배열의 연속된 k개의 합을 구하는 것이고, 인덱스를 하나씩 밀어가며 합을 구했다
  • 217ms

이렇게 하나씩 밀어가며 연속된 k개의 합을 구한다
이중 for문을 사용하는 것 보다 빠른 시간으로 문제를 풀 수 있다

---

삽질

for (int i=0; i<=(n-k); i++) {
    int sum = 0;
    for (int j=0; j<k; j++) {
        sum += (arr[j+i]);
        answer = Math.max(sum, answer);
    }
}

• 처음에 이중 for문으로 도전했는데, 시간초과가 됐다.
  • 1637ms