백준 수열 2559번 파이썬

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

2559번: 수열

 

 

풀이 

deque 을 이용해 풀었다. 다른 분들은 투포인터 등의 방법을 사용했던데 나는 deque 이 가장 직관적이라 느껴졌다.

우선 가장 단순하게 접근하면 리스트 슬라이싱을 먼저 떠올릴 수 있다. 하지만 입력의 최대 크기가 십만이기 때문에 당연히 시간초과 문제가 터진다. 이정도면 b급 영화의 뻔한 시놉시스보다 더 뻔한 전개가 아닐 수 없다. 클리셰를 극복하기 위해 나는 deque 를 사용했다.

 

우선 k 크기 만큼의 초기 배열을 deque로 구한다. 이를 init_arr 라 정의했다. init_arr 은 deque 다. double-ended queue 란 뜻이다. 즉 양쪽으로 넣고 빼고 할 수 있다. 이제 init_arr의 뒤쪽으로는 새로운 숫자를 넣으면서 동시에 맨 앞쪽의 원소는 popleft() 해준다. 이렇게 되면 O(n) 의 시간복잡도로 arr 를 순회하면서 init_arr 를 업데이트 할 수 있다. init_arr 은 deque 이기 때문에 append 나 popleft 모두 시간복잡도가 O(1) 이다.

 

코드

import sys
from collections import deque

input = sys.stdin.readline
n, k = map(int, input().split())

arr = list(map(int, input().split()))  # arr 의 길이 100_000
init_arr = deque()
for i in range(k):
    init_arr.append(arr[i])
init_sum = sum(init_arr)
result = init_sum
for i in range(k, len(arr)):
    pop = init_arr.popleft()
    init_sum -= pop
    new = arr[i]
    init_sum += new
    init_arr.append(new)

    result = max(result, init_sum)

print(result)