알고리즘
[백준 2559] 수열 Java 풀이
빠르게 핵심만
2024. 4. 22. 17:44
접근
n이 최대 100,000, k가 최대 100,000일 때, 이중 for 문으로 문제를 풀면 시간 복잡도가 O(n * k)가 되어 시간 초과가 발생합니다. 따라서 슬라이딩 윈도우 기법을 이용하여 시간 복잡도를 O(n)으로 줄여 문제를 해결할 수 있습니다.
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
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];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
// 초기 k일 동안 연속적인 온도의 합을 구한다.
int sum = 0, maxSum = 0;
for (int i = 0; i < k; i++) {
sum += arr[i];
}
// 슬라이딩 윈도우 기법을 이용하여 연속적인 온도의 합의 가장 큰 값을 구한다.
maxSum = sum;
for (int i = k; i < n; i++) {
sum += arr[i];
sum -= arr[i - k];
maxSum = Math.max(maxSum, sum);
}
// 결과 출력
System.out.println(maxSum);
}
}