백준 실버3 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이1]

⌛ 15분 (일부 케이스 시간 초과)

N, K = map(int,input().split())
nums = list(map(int,input().split()))
length = len(nums) #10
end = K #2
max_hap = 0

while end<=length:
    
    start = end-K

    now_hap = sum(nums[start:end])

    if now_hap>max_hap:
        max_hap = now_hap
    end += 1

print(max_hap)

수열이 주어지고 연속된 K개의 합들 중 최대값을 구하는 문제입니다.

최초 구현 시 시작점(start)와 끝점(end)을 정의한 뒤 해당하는 구간을 슬라이싱하고 매번 합을 구하는 방식으로 표현하였지만 일부 케이스에서 시간 초과가 발생하여 다른 방식을 고안하였습니다.

[나의 풀이2]

⌛ 34분

N, K = map(int,input().split())
nums = list(map(int,input().split()))
length = len(nums) #10
end = K #2
start = end-K
max_hap = sum(nums[start:end])
stack = [(nums[0],max_hap)]

while end<length:
    
    front ,before_hap = stack.pop()
    now_hap = before_hap-front+nums[end]

    if now_hap>=max_hap:
        max_hap = now_hap
    start += 1
    stack.append((nums[start],now_hap))    
    end += 1

print(max_hap)

'나의 풀이1'에서 while 한번 실행 될때마다 start~end 구간에 대해 sum() 함수를 실행하여 시간이 오래걸리는 방식을 개선하기 위해 stack 구조에 (맨 앞 요소, 현재구간의 합)을 기억하는 알고리즘으로 구현하였습니다.

다음 구간의 합은 이전 구간의 맨 앞 요소 1개를 빼고 맨 뒤 요소 +1 인덱스 값을 더하면 되기 때문입니다.

[다른 사람의 풀이]

n, k = map(int, input().split())
array = list(map(int, input().split()))
psum = [0] * (n+1)
s = 0

for i in range(n):
    s += array[i]
    psum[i+1] = s

ans = -int(1e9)

for i in range(k, n+1):
    ans = max(ans, psum[i]-psum[i-k])
print(ans)

누적 합을 활용한 풀이입니다. 입력된 수열의 첫 인덱스부터 각 i번 까지의 누적 합을 차례대로 저장한 psum을 구한 뒤

i번째 누적합에서 i-k번째 누적합을 뺄셈하면 K간격의 연속된 수열의 합을 비교할 수 있었습니다.

감사합니다.