백준) 2559 - 파이썬

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

(실버 3)

2559번: 수열

입력

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

 

 

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

출력

21

 

 

31

내 코드

import sys
input=sys.stdin.readline
n,k=map(int,input().split())
t=list(map(int,input().split()))
result=[]
for i in range(n):
    result.append(sum(t[i:i+k:]))
print(max(result))

시간 초과가 난 코드이다.

for문과 sum 사용으로 인한 O(n^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))

먼저 sum 함수를 일일이 실행하는 것이 아닌 처음에만 사용하고, 그 이후에는 배열 내 제일 앞에 있는 값을 빼고 정해진 길이(k)에서 한칸 뒤에 있는 값을 더하는 형태로 계산을 반복해서 결과값을 도출하였다.

sum 함수를 쓰지 않고 어떻게 구현할 수 있을까라는 생각을 조금만 더 해보면 나올 수 있을법한 답안이였다.

느낀 점

단순히 뭐하고 뭐해서 끝이 아닌 문제가 생겼으면 문제가 의심되는 부분을 어떻게 시간 복잡도를 줄일지 생각하는 과정이 필요할 듯 싶다.