최대 매출 구하기 및 슬라이딩 윈도우

문제.  A 공장의  총 N일 동안의 매출기록을 주고 연속된 K일 동안의 최대 매출액이 얼마인지 구하라고 했습니다.

 

입력 예시

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

 

 

나의 답변

import java.util.Scanner;

public class Main {	
	public int solution(int n, int k, int[] arr){
		int answer = 0; 
		for(int i=0; i<n-k; i++) {
			int index=i; 
			int sum=0; 
			int cnt=0; 
			while(cnt<k) {
				sum+=arr[index++]; 
				cnt++; 
			}
			if(sum > answer) {
				answer = sum; 
			}
		}
		return answer;
	}
	
	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int[] arr = new int[n]; 
		for( int i=0; i<n; i++ ) {
			arr[i] = sc.nextInt();
		}
		System.out.println(T.solution(n, k, arr));
	}
}

 

오답 : Time Limit Exceeded

이유 : 시간복잡도가 대략 O(N * K) 이다. O(N)으로 바꿀 수 있는 방법이 있다 

 

최대 매출 찾기에선 슬라이딩 윈도우를 사용하는 것이 유용하다 

 

슬라이딩 윈도우란?

슬라이딩 윈도우는 연속적인 요소들로 이루어진 고정 크기의 부분 배열이나 창을 통해 문제를 해결하는 알고리즘
1. 윈도우에 연속된 크기만큼 합을 구한다(초기 윈도우 설정)
2. 이 윈도우 맨 앞에 있는 수는 제외시키고 배열이 새로운 수는 합친다. (윈도우가 배열에서 이동하는 그림 생각하기)
3. 윈도우가 이동하면서 합은 계속 바뀌고 그 과정에서 최대값을 구한다.

 

 

정정 답변

import java.util.Scanner;

public class Main {	
	public 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) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int[] arr = new int[n]; 
		for( int i=0; i<n; i++ ) {
			arr[i] = sc.nextInt();
		}
		System.out.println(T.solution(n, k, arr));
	}
}