[Python] 백준 2559 수열

문제 분석

• 정수 수열에 대해 어느 기간 동안의 온도 합이 가장 큰지 확인

 

코드 설계

2차

• 제일 큰 수를 찾고 그 큰 수를 둘러싼 값 확인

 

정답 코드

1차 - 시간초과

import sys
input = sys.stdin.readline

n,k = map(int, input().split())
temp = list(map(int, input().split()))
s = 0
res = []

while s+k <= n:
    res.append(sum(temp[s:s+k]))
    s += 1
print(max(res))

 

2차 - 시간 초과

import sys
input = sys.stdin.readline

n,k = map(int, input().split())
temp = list(map(int, input().split()))
idx = temp.index(max(temp))
s = idx-k
res = []

while s+k <= n :
    res.append(sum(temp[s:s+k]))
    s += 1
print(max(res))

 

3차 - 런타임 에러

시간 효율을 위해 i번째 범위 합은 i-1번째 범위합에서 왼쪽 끝을 빼고 오른쪽 끝을 더해준다. (슬라이딩 윈도우)

import sys
input = sys.stdin.readline

n,k = map(int, input().split())
temp = list(map(int, input().split()))
idx = temp.index(max(temp))
s = idx-k+1
before = temp[s : s+k]
ans = [sum(before)]

while s+k < n:
    before.pop(0)
    after = before + [temp[s+k]]
    ans.append(sum(after))
    s += 1
    before = after

print(max(ans))

 

다른 사람 코드 1

import sys
input = sys.stdin.readline

n,k = map(int, input().split())
temp = list(map(int, input().split()))

part_sum = sum(temp[:k])
ans = part_sum

for i in range(n-k) :
    part_sum += temp[i+k] - temp[i]
    if ans < part_sum :
        ans = part_sum

print(ans)

 

다른 사람 풀이 2

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

part_sum = sum(tem_list[:K])
result_list = [part_sum]

for i in range(0, len(tem_list)-K):
    part_sum = part_sum - tem_list[i] + tem_list[i+K]
    result_list.append(part_sum)

print(max(result_list))