[PS] 인프런 강의 - Two Pointers, Sliding window, Math 3. 최대 매출

 

문제

현수의 아빠는 제과점을 운영합니다. 현수아빠는 현수에게 N일 동안의 매출기록을 주고 연속된 K일 동안의 최대 매출액이 얼마인지 구하라고 했습니다.
만약 N=10이고 10일 간의 매출기록이 아래와 같습니다. 이때 K=3이면

 

12 15 11 20 25 10 20 19 13 15

 

연속된 3일간의 최대 매출액은 11+20+25=56만원입니다. 여러분이 현수를 도와주세요.

 

▣ 입력설명
첫 줄에 N(5<=N<=100,000)과 K(2<=K<=N)가 주어집니다.
두 번째 줄에 N개의 숫자열이 주어집니다. 각 숫자는 500이하의 음이 아닌 정수입니다.

 

▣ 출력설명
첫 줄에 최대 매출액을 출력합니다.

 

▣ 입력예제 1
10 3
12 15 11 20 25 10 20 19 13 15

 

▣ 출력예제 1
56

 

풀이

내가 처음 푼 방식 처럼 이중 for문으로 풀면 O(n^2)이 되므로 n이 100,000일 때 k가 50,000이면 100,000 x 50,000 이 되버려서 시간 초과 에러가 난다.

 

그럼 어떻게 푸느냐

 

처음에 k개 만큼 누적합계를 sum 변수에 저장해두고, 그 다음 인덱스부터 i로 두고 for문을 돌면서

 

1. sum에 arr[i] 의 누적합을 더하고

2. sum에서 arr[i-k] 의 값을 뺀다

3. sum의 최대값을 구한다.

 

코드

1) 첨에 막푼 코드.. 시간초과 에러가 난다.

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		int n = in.nextInt();//n일
		int k = in.nextInt();//연속 k일
		int[] arr = new int[n];
		
		for(int i=0; i<n; i++) {
			arr[i] = in.nextInt();
		}
		
		int answer = Integer.MIN_VALUE;
		for(int i=0; i<n-k+1; i++) {
			int sum = 0;
			
			for(int j=i; j< i+k; j++) {
				sum += arr[j];
			}
			answer = Math.max(answer, sum);
		}
		
		System.out.print(answer);
	}
}

 

2) 강사님 코드

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		int n = in.nextInt();//n일
		int k = in.nextInt();//연속 k일
		int[] arr = new int[n];
		
		for(int i=0; i<n; i++) {
			arr[i] = in.nextInt();
		}
		
		int sum = 0;
		for(int i=0; i<k; i++) sum += arr[i];
	
		int answer = sum;
		for(int i=k; i<n; i++) {
			sum += arr[i];
			sum -= arr[i-k];
			answer = Math.max(answer, sum);
		}
		
		System.out.print(answer);
	}
}