(백준 알고리즘 문제풀이) 2559번 수열

문제

 

문제 링크

 

문제 접근

• N: 온도를 측정한 전체 날짜의 수
• K: 합을 구하기 위한 연속적인 날짜의 수
• 구하고자 하는 것: K일 동안의 온도의 합이 가장 큰 프로그램을 계산하는 프로그램

코드

시간초과 코드

import sys

N, K = map(int, sys.stdin.readline().split())

lst = list(map(int, sys.stdin.readline().split()))
# N-K+1는 K일동안 온도의 합을 구하는 집합의 원소의 개수

result = 0
for i in range(N-K+1):
    S = sum(lst[i:i+K])
    if result < S:
        result = S

print(result)

 

 

통과 코드

import sys

N, K = map(int, sys.stdin.readline().split())

lst = list(map(int, sys.stdin.readline().split()))
# N-K+1는 K일동안 온도의 합을 구하는 집합의 원소의 개수


result = sum(lst[0:K])
ans = result
for i in range(1, N-K+1):
    result = result - lst[i-1] + lst[i+K-1]
    if ans < result:
        ans = result

print(ans)

 

차이점

시간초과 코드는 loop안에서 sum함수를 사용하여 주었고 통과코드는 stack이 쌓일 때마다 첫번째 리스트를 빼주고 마지막 리스트를 추가시켜주는 형태로 index를 따라서 Loop를 통과하였다. 그 결과 시간 초과 문제가 해결되었다.

 

느낀점

간단한 코드도 메모리 할당과 시간 분할을 잘 시켜야할 것 같다. 분명 N이 100,000이하의 숫자는 엄청 크기 때문에 문제가 생길 가능성이 있었지만 그것에 대하여 간과하고 문제를 풀어 시간초과가 생긴 것 같다.