[슬라이딩윈도우] 최대 매출 (인프런 알고리즘 3-3)

문제 풀이 (JAVA)

import java.util.*;
public class part3_3 {

	public static void main(String[] args) {
		// 최대 매출
		Scanner input =new Scanner(System.in);
		
		int N = input.nextInt();
		int K = input.nextInt();
		
		int [] a = new int[N];
		for(int i=0; i<N; i++) {
			a[i]=input.nextInt();
		}
		int answer = solution(N,K,a);
		System.out.print(answer);
		
	}
	private static int solution(int N, int K, int [] a) {
		int result=0;
		int sum=0;
		for(int i=0; i<K; i++) {
			sum+=a[i];
		}
		result=sum; // 첫번째 윈도우 sum 계산
		int p1=K; // 포인터는 첫번째 윈도우 +1번째를 바라본다.
		while(p1 < N) {
			// 한칸씩 옮기며 마지막 행(p1)은 더하고 첫번째 행(p1-k)은 뺀다.
			sum += (a[p1] - a[p1-K]);
			if(result <sum) { // 해당 윈도우가 가장 크다면 값 변경
				result=sum;
			}
			p1++; //포인터 증가 
		}
		
		return result;
	}
}

주요 핵심 포인트

1.  슬라이딩 윈도우 알고리즘은 매번 비교하는 값이 1씩 증가하며 값을 구하는데, 1씩 증가할때마다 첫번째 값은 빼고, 증가한 마지막 값을 더해주어 값을 변경해주는 알고리즘으로 O(n^2)번을 O(n)번으로 축약시켜 효율성 테스트를 통과해야 하는 문제이다.