백준 2559번 - 수열 (파이썬/Python)

문제

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

예를 들어, 아래와 같이 10일 간의 온도가 주어졌을 때,

3 -2 -4 -9 0 3 7 13 8 -3

모든 연속적인 이틀간의 온도의 합은 아래와 같다.

문제 링크

https://www.acmicpc.net/problem/2559

2559번: 수열

틀린답안

N, K = map(int, input().split())
lst = list(map(int, input().split()))

max_V = 0 # 최댓값을 넣을 변수
for i in range(N-K+1): # 0부터 N-K+1만큼 반복
    if max_V < sum(lst[i:i+K]): # max_V가 lst[i]부터 lst[i+K-1]의 합보다 작으면
        max_V = sum(lst[i:i+K]) # max_V값 갱신
print(max_V)

슬라이싱을 이용했더니 시간초과가 났다,,, ^^

맞은답안

N, K = map(int, input().split())
lst = list(map(int, input().split()))

part_sum = sum(lst[:K])
answer = part_sum # part_sum 값을 answer에 저장

max_V = 0 # 최댓값을 넣을 변수
for i in range(N-K): # 0부터 N-K+1만큼 반복
    part_sum += lst[i+K]-lst[i] # part_sum 값에 lst의 i번째 값을 빼고, i+K번째 값을 더해준다.
    if answer < part_sum: # 그 값이 더 크면 answer 값 갱신
        answer = part_sum
    
print(answer)

후기

슬라이싱을 이용하는 것보다 슬라이딩 윈도우를 이용하는게 훨씬 속도가 빠르다.

 

슬라이딩 윈도우란?

일정한 범위를 가지는 것을 유지한 채 이동하며 계산되는 방법, 최소한의 데이터만을 활용하는 방법 (가장 작은 경우의 수부터 하나씩 이동하는 느낌으로 계산된 값을 누적해나가는 방법)

 

슬라이딩 윈도우는 아무래도 기존의 값을 가지고 추가하고 제거하는 방식이라 

매번 새롭게 값을 찾아야하는 슬라이싱보다 더 빠르군...

범위가 일정할때는 슬라이딩 윈도우, 다를땐 투 포인터!