문제
매일 측정한 온도가 N개 주어질 때, 연속적인 K일간의 온도 합이 최대가 되는 값을 구하라.
입력
첫째 줄에 N과 K가 주어진다. 둘째 줄에 N개의 온도가 주어진다.
출력
연속적인 K일의 온도 합 중 최댓값을 출력한다.
예제
| 입력 | 출력 |
|---|---|
10 2 -3 -14 -5 13 8 -11 -6 3 -1 7 | 21 |
풀이
슬라이딩 윈도우로 고정 길이 K인 구간의 합을 이동하며 최댓값을 구한다.
- 처음 K개 원소의 합을 구한다
- 윈도우를 한 칸씩 오른쪽으로 이동하며 새 원소를 더하고 빠지는 원소를 뺀다
- 매 이동마다 최댓값을 갱신한다
핵심 아이디어: 윈도우를 한 칸 이동할 때 O(1)에 합을 갱신할 수 있어 전체 O(N)에 해결된다.
코드
package day599;
import java.io.*;
import java.util.*;
public class Day576BOJ2559수열 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int[] arr = new int[n + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= n; i++)
arr[i] = Integer.parseInt(st.nextToken());
int i = 1;
int sum = 0;
while (i <= k)
sum += arr[i++];
int max = sum;
while (i <= n) {
sum += arr[i] - arr[i - k];
if (max < sum)
max = sum;
i++;
}
System.out.println(max);
}
}복잡도
- 시간: O(N)
- 공간: O(N)