java - 최대 매출(슬라이딩 윈도우)

 

import java.util.Scanner;

// 슬라이딩 윈도우
public class MaximumRevenue {
    public static int solution(int k, int[] incomes) {
        int sum = 0, lt = 0, rt = 0, max = 0;
        while (rt < incomes.length) {
            if (rt < k) {
                sum += incomes[rt++];
                continue;
            }
            if (sum > max) max = sum;
            sum -= incomes[lt++];
            sum += incomes[rt++];
        }
        return max;
    }

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

 

문제 풀이

---

이문제 같은 경우 2중 for문으로 해결 할수 있지만 그렇게 되면 시간복잡도가 O(n)의 제곱이 되기 때문에

2 point 를 사용하여 O(n)에 해결해야 한다.

 

이문제 같은경우를 슬라이딩 윈도우라고 하는데 배열의 i ~ j 까지의 합을 유지한채 한칸씩 밀고 나가는 방식이다.

예시에서 3일치의 최대합을 구해야 하기 때문에 index 0 ~ 2 까지의 합을 구한뒤

한칸씩 밀고 나가면서 0 번 값을 빼주고 2 + 1 값을 더한다.

 

요기서 주의해야 할점은 0 ~ 2 번에서 1 ~ 3 번으로 넘어 갈때 0번을 빼고 3번을 더해야 한다는 점이다.