언제 쓰나
- “연속한 K개의 합/최대/최소/개수” — 크기가 고정된 구간을 훑는 문제
- “길이 K인 부분 문자열 중 조건을 만족하는 것” — 문자 빈도를 유지하며 밀기
- 매 위치에서 K개를 다시 세는
O(n × K)풀이가 시간 초과일 때
투포인터와 형제 기법이다. 투포인터는 구간 크기가 조건에 따라 변하고, 슬라이딩 윈도우는 크기를 고정한 채 민다.
핵심 아이디어
창문을 한 칸 밀 때 전체를 다시 계산하지 않는다. 빠지는 값 하나를 빼고, 새로 들어오는 값 하나를 더한다.
arr = [2, 5, 1, 8, 3] k = 3
[2 5 1] 8 3 sum = 8
└─────┘
2 [5 1 8] 3 sum = 8 - 2 + 8 = 14
└─────┘ 빠진 값 새 값
2 5 [1 8 3] sum = 14 - 5 + 3 = 12
└─────┘
매 칸 O(1) × n칸 = O(n) (매번 다시 더하면 O(nk))코드 템플릿
“연속 K개의 합의 최댓값” — 기본 꼴.
def max_window_sum(arr, k):
window = sum(arr[:k]) # 첫 윈도우만 통째로
best = window
for i in range(k, len(arr)):
window += arr[i] - arr[i - k] # 새 값 더하고 빠진 값 빼기
best = max(best, window)
return best문자열 빈도 유지형 — “길이 K 구간의 문자 구성이 조건을 만족하는가”류.
from collections import Counter
def count_valid(s, k, ok): # ok(counter): 조건 검사
counter = Counter(s[:k])
result = 1 if ok(counter) else 0
for i in range(k, len(s)):
counter[s[i]] += 1 # 들어오는 문자
counter[s[i - k]] -= 1 # 나가는 문자
if ok(counter):
result += 1
return result풀이 과정 따라가기
[2, 5, 1, 8, 3]에서 연속 3개의 합의 최댓값을 찾는 과정이다.
함정
- 경계 off-by-one. 한 칸 밀 때 빠지는 인덱스는
i - k다.i - k + 1이나i - k - 1로 쓰면 예제 몇 개는 통과해서 찾기 어렵다. - 첫 윈도우 처리. 반복문 시작 전에
arr[:k]로 초기 윈도우를 만들어야 한다. 반복문 안에서 처리하려다 이중 계산이 자주 난다. - 윈도우 안의 최대/최소는 덧셈처럼 안 된다. 나간 값이 최대값이었으면 나머지에서 다시 찾아야 하므로, 단순 갱신으로는 안 되고 모노톤 덱 같은 보조 구조가 필요하다.