문제
현수의 아빠는 제과점을 운영합니다. 현수 아빠는 현수에게 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이하의 음이 아닌 정수입니다.
출력
첫 줄에 최대 매출액을 출력합니다.
예시 입력
10 3
12 15 11 20 25 10 20 19 13 15
예시 출력
56
내 풀이
private static int getMaxSales(int day, int k, int[] sales) {
int max = 0, sum = 0;
// 첫 k일 동안의 합
for (int i = 0; i < k; i++) {
sum += sales[i];
}
max = sum;
for (int i = k; i < day; i++) {
// K일의 맨 앞 매출을 빼고 새 매출을 더한다
sum += -sales[i-k] + sales[i];
max = Math.max(max, sum);
}
return max;
}
매번 K개를 더하는 경우 시간제한에 걸린다.
K개의 합을 유지하면서 이전값을 빼고 새 값을 더한다
12 15 11 20 // sum 초기값 = 12+15+11 = 38
12 15 11 20 // sum = sum -12 + 20 = 46
'Java > Coding-Test' 카테고리의 다른 글
[Java] 3-5 연속된 자연수의 합 (0) | 2022.01.22 |
---|---|
[Java] 3-4 연속 부분수열 (0) | 2022.01.20 |
[Java] 3-2 공통원소 구하기 (0) | 2022.01.19 |
[Java] 3-1 두 배열 합치기 (0) | 2022.01.19 |
[Java] 2-12 멘토링 (0) | 2022.01.18 |
댓글