[백준 2559] 수열 Java 풀이

2559번: 수열

 

접근

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);
	}
}