문제 요약
길이 N인 온도 수열이 주어질 때, 연속한 K일의 온도 합 중 최댓값을 구하는 문제다.
N은 최대 100,000- 온도는 음수도 가능
- 모든 길이
K구간을 확인해야 함
즉, 연속 구간의 합을 빠르게 갱신하는 방식이 중요하다.
내가 푼 흐름
이전 문제인 구간 합 구하기 4에서 배운 아이디어를 바로 적용해서 풀었다.
처음 K개의 합을 한 번 구한 뒤,
그 다음 구간부터는 매번 다시 sum()을 하지 않고
- 맨 앞 값을 빼고
- 새로 들어오는 값을 더하는 방식
으로 다음 구간 합을 갱신했다.
누적합 문제를 막 풀고 와서 그런지, 이번 문제는 비교적 쉽게 풀렸다.
핵심 아이디어
길이 K인 첫 구간의 합을 먼저 구한다.
sum(nums[:k])
그다음, 한 칸 오른쪽으로 이동한 구간의 합은 이전 합에서 다음처럼 갱신할 수 있다.
- 빠지는 값:
nums[i-1] - 새로 들어오는 값:
nums[i+k-1]
즉,
이전 구간 합 - 빠지는 값 + 새로 들어오는 값
으로 다음 구간 합을 O(1)에 구할 수 있다.
이 방식을 보통 슬라이딩 윈도우(sliding window) 라고 부른다.
왜 이 방식이 빠른가?
모든 구간마다 sum(nums[i:i+k])를 하면,
구간 하나를 계산할 때마다 최대 K번 덧셈이 필요하다.
그러면 전체 시간 복잡도는 대략 O(NK)가 될 수 있다.
반면 지금 방식은
- 첫 구간 합 계산:
O(K) - 나머지 구간들 갱신:
O(N)
이므로 전체가 O(N) 수준으로 해결된다.
내 코드
n, k = map(int, input().split())
nums = list(map(int, input().split()))
sums = [sum(nums[:k])]
for i in range(1, n-k+1):
sums.append(sums[i-1] - nums[i-1] + nums[i+k-1])
print(max(sums))
더 줄여볼 수 있는 포인트
현재 코드도 정답이고 충분히 통과된다.
다만 sums 리스트에 모든 구간 합을 저장하지 않고,
현재 구간 합과 최댓값만 관리해도 된다.
즉,
- 현재 윈도우 합
- 지금까지의 최대값
이 두 개만 있으면 되므로 메모리를 더 아낄 수 있다.
이 문제에서는 지금 코드도 충분히 깔끔하고 좋다.
이번 문제로 배운 점
- 연속 구간의 합 문제는 누적합이나 슬라이딩 윈도우로 연결되는 경우가 많다.
- 매 구간마다
sum()을 다시 호출하면 느릴 수 있다. - 고정 길이 구간의 최댓값/최솟값 문제에서는
이전 구간에서 한 칸 이동했을 때 무엇이 빠지고 무엇이 들어오는지를 생각하면 된다. - 이전 문제에서 배운 아이디어를 바로 다음 문제에 적용해보는 과정이 꽤 도움이 된다.