https://www.acmicpc.net/problem/2559
(실버 3)
입력
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 함수를 쓰지 않고 어떻게 구현할 수 있을까라는 생각을 조금만 더 해보면 나올 수 있을법한 답안이였다.
느낀 점
단순히 뭐하고 뭐해서 끝이 아닌 문제가 생겼으면 문제가 의심되는 부분을 어떻게 시간 복잡도를 줄일지 생각하는 과정이 필요할 듯 싶다.
'알고리즘 공부 > 연습 문제' 카테고리의 다른 글
백준) 11723 - 파이썬 (0) | 2023.09.06 |
---|---|
백준) 2635 - 파이썬 (0) | 2023.09.06 |
SW Expert Academy) 17299. 최소 덧셈-파이썬 (0) | 2023.08.16 |
백준) 1920 - 파이썬 (0) | 2023.08.08 |
백준) 11399 - 파이썬 (0) | 2023.07.27 |