[백준] 2559 : 수열 - Java

• 백준 문제 URL

---

문제 요약

연속된 k일 동안의 온도 합이 가장 큰 값을 구하는 문제다.

즉,

• 배열 dayTemp에서 길이가 정확히 k인
• 연속된 부분합의 최대값을 찾아야 한다.

---

핵심 아이디어

이 문제는 단순히 모든 연속 구간을 확인하면 (O(n^2))이 되지만,
슬라이딩 윈도우(Sliding Window) 기법으로 (O(n))에 해결할 수 있다.

핵심은 윈도우를 이동시키면서 합을 효율적으로 갱신하는 것이다:

1. 처음 k일의 합을 계산.
2. 윈도우를 오른쪽으로 1칸 이동할 때마다
   • 오른쪽 끝에 새로 추가되는 값을 더하고
   • 왼쪽 끝에서 빠져나가는 값을 빼서 합 갱신.

---

알고리즘 핵심 로직

1. 초기 윈도우 [0, k-1] 합 계산
2. for i = 1 to n-k:
   currentSum = currentSum - arr[i-1] + arr[i+k-1]
   maxSum = max(maxSum, currentSum)

핵심:

• 매번 처음부터 합을 다시 계산하지 않고,
• 차감 + 추가 로 윈도우 이동 시 합을 (O(1))에 갱신한다.

---

전체 코드 (제출용)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        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[] dayTemp = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            dayTemp[i] = Integer.parseInt(st.nextToken());
        }

        int maxSum = Integer.MIN_VALUE;
        int currentSum = 0;

        // 초기 윈도우 합 계산
        for (int i = 0; i < k; i++) {
            currentSum += dayTemp[i];
        }
        maxSum = currentSum;

        // 윈도우 이동하며 갱신
        for (int i = 1; i <= n - k; i++) {
            currentSum += dayTemp[i + k - 1] - dayTemp[i - 1];
            maxSum = Math.max(maxSum, currentSum);
        }

        System.out.println(maxSum);
    }
}

---

예제 시뮬레이션

입력:

n = 10, k = 3
dayTemp = [1, -1, -2, 5, 4, -3, 3, 2, 0, 1]

윈도우	구간	합	maxSum
1	[0:2]	1-1-2 = -2	-2
2	[1:3]	-1-2+5 = 2	2
3	[2:4]	-2+5+4 = 7	7
4	[3:5]	5+4-3 = 6	7
5	[4:6]	4-3+3 = 4	7

최종 결과: 7

---

핵심 포인트 정리

• 슬라이딩 윈도우의 대표적인 예제
• 고정 길이 윈도우에서 최대 합 찾기
• O(1) 윈도우 이동 → currentSum += 새값 - 빠지는값
• 시간 복잡도: (O(n))