Sliding Window

<백준 2559번 문제>
매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다.

매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오.

버블 탐색을 하면 시간 초과 에러가 난다...
최악의 경우 O(n^2)의 시간 복잡도가 나올 수 있기 때문에

n,t = map(int,input().split())
arr = list(map(int,input().split()))

Max=-21e8

for i in range(n-t+1):
    Sum = 0
    for j in range(i,i+t):
        Sum += arr[j]

    if Max < Sum :
        Max = Sum

print(Max)

어떻게 해결해주어야 할까?
=> 슬라이딩 윈도우를 사용하자.

슬라이딩 윈도우

맨 앞의 값을 더해주고 뒤를 빼준다.
이런식으로 한다면 O(n)으로 설정이 가능하다.

# 슬라이딩 윈도우
def maxSlidingWindow(nums,t,k):
    Max_sum = -21e8
    window_sum = 0
    start = 0

    for end in range(t):
        window_sum += nums[end] # 끝에 더해주고

        if end >= k - 1:
            # 0~k-1 까지 더한 값이 최소값보다 작다면, 최소값을 갱신
            if window_sum >= Max_sum:
                Max_sum= window_sum

            # 윈도우에 포함된 맨 앞자리 수를 제거
            window_sum -= nums[start] # 앞에 빼준다
            # 윈도우 시작 인덱스를 하나 증가
            start += 1

    return Max_sum


t,k = map(int,input().split())
nums = list(map(int,input().split()))
ret=maxSlidingWindow(nums,t,k)
print(ret)

해결완료!