[Inflearn]_최대 매출

인프런의 자바(Java)알고리즘 문제풀이 입문:코딩테스트 대비 강좌의 문제를 풀고 문제 해설을 작성해보았습니다.

 

섹션 3. Two pointers, Sliding window[효율성 : O(n^2)-->O(n)]의 3. 최대 매출(Sliding window) 강의편 입니다.

 

설명

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

만약 N=10이고 10일 간의 매출기록이 아래와 같습니다. 이때 K=3이면

12 1511 20 2510 20 19 13 15

연속된 3일간의 최대 매출액은 11+20+25=56만원입니다.

여러분이 현수를 도와주세요.

 

입력

첫 줄에 N(5<=N<=100,000)과 K(2<=K<=N)가 주어집니다.

두 번째 줄에 N개의 숫자열이 주어집니다. 각 숫자는 500이하의 음이 아닌 정수입니다.

 

출력

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

 

import java.util.Scanner;

public class 최대_매출 {
	public static void main(String[] args) {
		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(solution(n, k, arr));
	}
	
	public static int solution(int n, int k, int[] arr) {
		int ans = 0, sum = 0;
		for(int i=0; i<k; i++) sum+=arr[i];
		ans = sum;
		for(int i=k; i<n; i++) {
			sum+=(arr[i]-arr[i-k]);
			ans = Math.max(ans, sum);
		}
		
		return ans;
	}
}

 

 

>>해설

[main 메소드]

n: 매출 기록의 일수

k : 최대 매출액 지정 일수

arr : n일 동안의 매출 기록

-> scanner 를 통해 값을 입력 받음.

 

[solution 메소드]

먼저 arr에서 k까지 각각의 배열 요소를 sum에 누적시킨다.

그리고 ans 변수에 sum값을 넣고

i를 k부터 n까지 반복하면서

sum에 arr의 i번째 배열 요소를 더하고 arr의 i번째에서 k만큼 뺀 배열의 요소를 뺀다.

그리고 ans와 sum 둘 중에서 최대값을 ans에 저장하고 리턴시킨다.