---
title: "슬라이딩 윈도: 연속 구간의 중복 계산과 단조성 경계를 분리하기"
slug: "java-sliding-window"
category: "CS"
topic: "cs"
subtopic: "problem-solving-patterns"
tags: ["Java","Sliding Window","Two Pointers","Stream","Invariant"]
status: "published"
created: "2026-08-06"
updated: "2026-08-06"
summary: "고정 길이 합과 양수 배열의 가변 길이 창을 분리하고, 창 상태 불변식·음수 반례·long 누적합·stream buffer 비용을 Java로 검증한다."
kind: "Deep Dive"
evidence: "JLS 21 정수 연산·Java 배열/JVMS 21을 대조하고 SlidingWindowDemo의 고정·가변·빈 입력·실패 계약을 OpenJDK 21.0.11에서 실행"
series: "Java Essential Algorithms"
---

길이 $k$인 모든 연속 구간 합을 매번 처음부터 더하면 인접한 두 구간의 $k-1$개 원소를 중복 계산한다. 슬라이딩 윈도는 나가는 값과 들어오는 값만 반영해 이 중복을 제거한다. 다만 가변 길이 창은 값의 부호 같은 추가 단조성이 필요하다.

## 1. 두 문제의 계약을 섞지 않는다

1. `maxFixedWindowSum(values,width)`: 정확히 width개인 연속 구간 중 최대 합을 반환한다. width가 0 이하이거나 배열보다 크면 계약 위반이다.
2. `minLengthAtLeast(positive,target)`: **모든 값이 양수**일 때 합이 target 이상인 가장 짧은 연속 구간 길이를 반환한다. 없으면 0이다.

고정 창은 음수도 허용한다. 가변 창은 음수가 있으면 left를 줄였을 때 합이 오히려 커질 수 있어 현재 이동 규칙이 무너진다. 이름이 같은 패턴이라고 전제를 공유하지 않는다.

## 2. 고정 창 상태 전이

`[2,-1,3,5,-2]`, width 3을 본다.

| 창 index | 원소 | 이전 합에서 제거/추가 | 현재 합 | best |
| --- | --- | --- | ---: | ---: |
| `[0,3)` | `2,-1,3` | 초기 3개 합 | 4 | 4 |
| `[1,4)` | `-1,3,5` | `-2 +5` | 7 | 7 |
| `[2,5)` | `3,5,-2` | `-(-1) -2` | 6 | 7 |

**불변식:** right를 처리한 뒤 `current`는 정확히 마지막 width개 값의 합이고 `best`는 지금까지 완성된 모든 width 창의 최대 합이다. 이전 창에서 빠지는 `values[right-width]`를 빼고 새 값을 더하면 겹치는 원소를 다시 더하지 않아도 정확하다.

## 3. 양수 가변 창의 이동 증명

`[2,3,1,2,4,3]`, target 7에서 right를 늘리며 합을 키운다. 합이 7 이상이면 left를 오른쪽으로 옮겨 가능한 한 줄인다. 모든 값이 양수이므로 right를 고정했을 때 left를 옮길수록 합은 단조 감소한다.

**불변식:** 내부 while 종료 후 현재 window 합은 target보다 작고, 그 직전에 제거한 left를 포함한 창들은 해당 right에서 가능한 target 이상 후보로 평가됐다. 각 left/right가 되돌아가지 않으므로 모든 최소 후보를 놓치지 않는다.

음수 반례 `[2,-1,2]`, target 3에서는 합이 target 미만이라고 right만 늘리는 규칙의 의미가 흔들리고, left 제거가 합을 키울 수도 있다. 일반 정수 배열의 shortest subarray는 prefix sum과 monotonic deque 같은 다른 알고리즘이 필요하다.

## 실행 재현

아래 코드는 설명용 조각이 아니라 `main`에 정상·빈 입력·중복·경계·실패 계약을 함께 넣은 완전한 Java 21 프로그램이다.

```java
public final class SlidingWindowDemo {
    static long maxFixedWindowSum(int[] values, int width) {
        if (values == null) throw new IllegalArgumentException("values must not be null");
        if (width <= 0 || width > values.length) throw new IllegalArgumentException("invalid width");
        long current = 0;
        for (int i = 0; i < width; i++) current += values[i];
        long best = current;
        for (int right = width; right < values.length; right++) {
            current += values[right];
            current -= values[right - width];
            best = Math.max(best, current);
        }
        return best;
    }

    static int minLengthAtLeast(int[] positive, long target) {
        if (positive == null) throw new IllegalArgumentException("positive must not be null");
        if (target <= 0) throw new IllegalArgumentException("target must be positive");
        long sum = 0;
        int left = 0;
        int best = Integer.MAX_VALUE;
        for (int right = 0; right < positive.length; right++) {
            if (positive[right] <= 0) throw new IllegalArgumentException("all values must be positive");
            sum += positive[right];
            while (sum >= target) {
                best = Math.min(best, right - left + 1);
                sum -= positive[left++];
            }
        }
        return best == Integer.MAX_VALUE ? 0 : best;
    }

    static void check(boolean condition, String message) {
        if (!condition) throw new AssertionError(message);
    }

    public static void main(String[] args) {
        check(maxFixedWindowSum(new int[] {2, -1, 3, 5, -2}, 3) == 7, "fixed");
        check(minLengthAtLeast(new int[] {2, 3, 1, 2, 4, 3}, 7) == 2, "variable");
        check(minLengthAtLeast(new int[0], 7) == 0, "empty");
        System.out.println("fixed max=7, variable minLength=2, missing=0");
    }
}
```

```bash
javac --release 21 SlidingWindowDemo.java
java SlidingWindowDemo
```

직접 실행한 출력은 다음과 같다.

```text
fixed max=7, variable minLength=2, missing=0
```

컴파일러와 런타임은 `javac 21.0.11`, OpenJDK `21.0.11`을 사용했다. `assert` 옵션에 의존하지 않고 실패 시 `AssertionError`를 던지므로 위 명령 그대로 검증된다.


## 4. 누적합 overflow와 실패 입력

width가 크면 `int` 원소의 합이 int 범위를 쉽게 넘는다. `long current`에 `int`를 더해 64-bit로 계산한다. 그래도 데이터 규모가 long 범위를 넘을 수 있는 도메인이면 `Math.addExact`나 더 큰 수 타입, overflow 정책이 필요하다.

가변 method는 non-positive 원소를 조용히 처리하지 않고 예외로 거절한다. 잘못된 전제에서 그럴듯한 답을 반환하는 것보다 failure를 계약으로 드러내는 편이 안전하다.

## 5. 복잡도 유도

고정 창은 초기 width개를 더하고 나머지 $n-width$개를 한 번 처리하므로 $\Theta(n)$이다. 가변 창은 right가 $n$번, left가 최대 $n$번 움직여 합계 최대 $2n$회이므로 $O(n)$이다. 중첩 while이 보여도 pointer가 되돌아가지 않아 $O(n^2)$가 아니다.

배열 batch 구현의 보조 공간은 $O(1)$이다. 실제 stream에서 나가는 값을 빼려면 최근 width개를 ring buffer에 보관해야 하므로 $O(width)$ 메모리가 필요하다. 입력 배열을 이미 가진 경우와 streaming state를 구분한다.

## 6. JVM과 allocation

예제 loop는 primitive `long/int`만 갱신하고 새 객체를 만들지 않는다. 입력 `int[]`는 heap에 있고 local references/index는 frame 관점이다. stream API로 매 원소를 boxing하거나 window subList를 매번 만들면 논리상 $O(n)$이어도 allocation과 GC pressure가 커질 수 있다. JFR로 allocation source를 확인한다.

## 7. prefix sum·two pointers·deque와 비교

| 선택 | 질의/전제 | 시간 | 상태 |
| --- | --- | ---: | ---: |
| 고정 sliding sum | 한 번 전체 scan | $O(n)$ | $O(1)$ batch |
| prefix sum | 여러 range-sum 질의 | build $O(n)$, query $O(1)$ | $O(n)$ |
| 양수 가변 window | 합 단조성 | $O(n)$ | $O(1)$ |
| monotonic deque | window min/max 또는 일반 prefix 조건 | $O(n)$ | $O(n)$ 최악 |

반복 range query라면 prefix sum 구축이 낫고, 모든 window의 최댓값 원소를 구하려면 합 한 개가 아니라 monotonic deque가 필요하다.

## 8. 실제 도메인 적용

rate-limit의 최근 60초 요청, telemetry moving aggregate, stream anomaly window에 쓸 수 있다. 그러나 processing-time과 event-time을 구분하고 late/out-of-order event, watermark, state TTL을 설계해야 한다. 관측 지표는 active windows, state bytes, late-event ratio, eviction lag, overflow/rejection이다.

## 9. 이건 피한다

- **음수 배열에 양수 전용 가변 window를 쓴다.** 합의 단조성이 깨져 정답을 놓친다. prefix sum+deque 등 계약에 맞는 알고리즘을 쓴다.
- **매 창을 `copyOfRange`로 만든다.** $O(nk)$ 복사와 allocation을 만든다. 나가는 값/들어오는 값만 갱신한다.
- **합을 int에 둔다.** 큰 window에서 overflow가 최대 비교를 왜곡한다. long 또는 명시적 overflow 정책을 쓴다.
- **batch 보조 공간 $O(1)$을 stream에도 그대로 쓴다.** 나가는 값을 기억할 buffer가 필요하다. window state와 TTL을 산정한다.
- **width 오류를 0으로 반환한다.** 실제 최대합 0과 계약 위반이 섞인다. 예외나 명시적 result로 구분한다.

## Reference

- Oracle, [The Java Language Specification, Java SE 21 — Integer Operations](https://docs.oracle.com/javase/specs/jls/se21/html/jls-4.html#jls-4.2.2)
- Oracle, [Arrays — Java SE 21 API](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/Arrays.html)
- Oracle, [ArrayDeque — Java SE 21 API](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/ArrayDeque.html)
- Oracle, [The Java Virtual Machine Specification, Java SE 21 — Heap and Frames](https://docs.oracle.com/javase/specs/jvms/se21/html/jvms-2.html#jvms-2.5)