최대 매출 (Sliding window)

Sliding Window란?

미끄러지는 창문?
연속된 k일 동안, 예를 들어 금토일, 토일월, 일월화 처럼 요일중 어떤 일정한 규칙의 연속된 자료의 최댓값이나 최솟값을 구할때 유용할 것같다.
1 2 3 4 5 6 7 8 9...n | 월 화 수 목 금 토 일 월 화 ...n 에서 초기값이
[]라는 창문이 존재한다고 생각하면 쉽다.
k가 3이라면, 첫 창문은 [1][2][3] 이렇게 감싸고있다.
첫창문과 다음창문을 비교하면
[1][2][3] vs [2][3][4]이다.
또 다음창문과 다다음창문을 비교해나가면서 전부 비교할수있다.
Sliding Window를 사용하면 O(n) 번의 탐색을 통해 답을 구할수있다.
즉, 10만개의 자료가 있다면 10만번만 탐색하면 답을 알아낼수있다.

문제

나의풀이

import java.util.*;

class Main {
	public int solution(int n,int k, int[] arr) {
			int answer = 0, sum = 0;
			int max = 0;
			for (int i = 0; i < k; i++) sum += arr[i]; max = sum;//초기 합
			for (int i = 0; i < n-k; i++) {
				sum = sum - arr[i] + arr[i+k];
				max = Math.max(sum, max);
			}
			/* 이방법도 가능
			for (int i = k; i < n; i++) {
				sum += (arr[i] - arr[i-k]);
				max = Math.max(sum, max);
			}
			 */
			answer = max;
			return answer;
		}
		    
	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt(); 
		int[] arr = new int[n];
		int m = kb.nextInt();
		for (int i = 0; i < n; i++) {
			arr[i] = kb.nextInt();
		}
		System.out.println(T.solution(n, m, arr));
	}
	
}

풀이방법

처음엔 2중 for문을 돌려서 풀어봤지만, 시간초과 에러가 나면서 통과하지 못했다.
2중 for문은 O(n^2)의 시간이 들지만 Sliding Window를 활용하면 O(n)의 시간으로 획기적이게 단축시킬수있다.
먼저 가장 초기값을 k길이까지 더해서 sum에 설정시켜줬다.
그 후 0~2번창문 vs 1~3번창문 끼리 값을 비교후 더 큰 창문의 값을 max에 저장하고
1~3vs2~4 .. 2~4vs3~5 ... (i-k-1) ~ (i+k) vs (i-k) ~ (i+k+1) 과정을 통해
최댓값을 max에 담았다.

핵심키워드

Sliding Window를 통해 풀수있는 알고리즘은 2중for문을 피해서 시간단축을 위한 풀이를 하자!
창문에 값을 담고 미끄러진다고 생각!