[알고리즘] 3-3 최대 매출 - sliding window 알고리즘(인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의)

인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 간략한 문제 설명, 예습 풀이 코드, 강의에서 설명하는 풀이 코드를 정리하고 있습니다.

• 문제 링크 : https://cote.inflearn.com/contest/10/problem/03-03
• 문제 설명 : N일 동안의 제과점 일매출 기록에서 연속된 K일 동안의 최대 매출액이 얼마인지 구하는 문제

예습 풀이

• 단순하게 이중 for 문을 사용하여 풀이

package inflearn.tow_pointers_sliding_window;

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

public class Main3_3 {

    public static int solution(int n, int k, int[] arr) {
        int answer = 0;

        for (int i = 0; i < n - k; i++) {
            int sum = 0;

            //i~(i+k) 날까지의 매출액
            for (int j = i; j < i + k; j++) {
                sum += arr[j];
            }

            if (sum > answer) {
                answer = sum;
            }
        }

        return answer;
    }

    public static void main(String[] args) throws IOException {
        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(solution(n, k, arr));
    }
}

강의 풀이

• sliding window 알고리즘 사용 -> 시간복잡도 O(n)
• 아래 그림처럼 먼저 0~k 날의 매출합을 구하고, 한칸씩 이동하면서 최댓값을 구한다.

• 강의를 듣기전 예습 풀이를 해보면서 이런 풀이 방법은 전혀 상상도 못했다...

public static int solution2(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;
}