백준 2559(시간 초과 나기 쉬운 문제)

 

 

 

처음 시도한 코드(시간 초과)

 

a, b = map(int, input().split())

temp = list(map(int, input().split()))

number = []

num = 0
for i in range(len(temp)):
  for j in range(i, i + b):
    if i + b > a:
      break
    num += temp[j]
  number.append(num)
  num = 0

number.pop(a-1)
print(max(number))

 

두 번째 시도한 코드(시간 초과)

 

import sys

a, b = map(int, sys.stdin.readline().split())

temp = list(map(int, sys.stdin.readline().rstrip().split()))

max_num = 0

for i in range(len(temp) - 1):
  max_num= max(max_num, sum(temp[i : i+b]))
  
print(max_num)

 

시간 제한이 1초인 문제인데,

 

시간 초과가 난다.

 

첫 번째 코드는 심지어 이중 반복문이니, 차치하고

 

두 번째 코드의 문제점은

 

모든 부분 수열을 구하고 각 부분 수열의 합을 계산하여 최댓값을 찾는 방식을 사용하기 때문에,

 

시간 복잡도가 O(N^2)이다.

 

문제의 엣지 케이스는 100,000이기 때문에

 

약 100억의 연산이 일어나므로, 시간 초과가 나는 것이다.

 

 

최종 코드

 

import sys

a, b = map(int, sys.stdin.readline().split())

temp = list(map(int, sys.stdin.readline().rstrip().split()))

window_sum = sum(temp[:b])
max_sum = window_sum

for i in range(b, len(temp)):
    window_sum = window_sum + temp[i] - temp[i-b]
    max_sum = max(max_sum, window_sum)

print(max_sum)

 

이러한 시간 초과를 방지하기 위해서는,

 

위의 코드처럼

 

투 포인트(Two Pointers)

 

or

 

슬라이딩 윈도우(Sliding Window)

 

와 같은 기법을 사용해야 한다.