[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이하의 음이 아닌 정수입니다.

 

 

 

출력

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

 

 

 

예시 입력1

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

 

 

 

예시 출력1

56

 

 

 

 

 

풀이

[sliding window]

K가 3인 경우를 생각해보면, 길이가 3인 창을 하나 만든다고 생각하고 이것을 창문이라고 생각하자. 이 창문을 옆으로 쭉 밀고 가면 된다.

 

[시간복잡도]
이중 for문을 사용하면 시간복잡도가 n 제곱이 된다. 우리는 시간복잡도가 n이 되도록 해야한다.

 

[로직]
0부터 K전까지의 합을 구해놓고 이 값이 answer로 초기화 되도록 한다.
반복문은 i가 K부터 도는데, sum = sum + arr[i] - arr[i-K] 예를 들어, K=3일 때, 첫 번째 반복에서는 arr[3]을 더하고 arr[0]을 빼는 것이다.

그리고 더 큰 값을 고르면 되는데, Math.max를 사용했다.

 

 

코드

package inflearn._3_3;

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

public class Main {

    public static int solution(int n, int k, int [] arr) {

        int answer = 0, sum = 0;

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

        answer = sum;

        for(int i = k; i < n; i++) {
            sum += (arr[i] - arr[i-k]);
            answer = Math.max(answer, sum); // 더 큰 값 고르기
        }

        return answer;

    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        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; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        bw.write(sb.append(solution(N, K, arr)).toString());
        bw.flush();

        bw.close();
        br.close();
    }
}