백준 | 블로그

백준 블로그

import sys

n, x = map(int, sys.stdin.readline().split())
visitors = list(map(int, sys.stdin.readline().split()))

# 슬라이딩 윈도우
current_window_sum = sum(visitors[:x])
max_window_sum = current_window_sum
max_window_count = 1
for i in range(1, n - x + 1):
    current_window_sum -= visitors[i - 1]
    current_window_sum += visitors[i + x - 1]

    if current_window_sum == max_window_sum:
        max_window_count += 1
    elif current_window_sum > max_window_sum:
        max_window_sum = current_window_sum
        max_window_count = 1

if max_window_sum == 0:
    print("SAD")
else:
    print(max_window_sum)
    print(max_window_count)

가장 쉽게 떠올릴 수 있는 아래와 같은 코드는 시간 초과가 뜬다.
왜 그럴까?

sum(visitors[:x])의 계산은 슬라이싱과 합계가 순차적으로 실행되므로 O(x)이다.
그런데 for 문 안에서의 작업이므로 O((n - x + 1) X x)의 시간 복잡도를 갖게 된다.
주어진 범위가 1 <= x <= n <= 250,000이기 때문에, 최악의 경우 1초를 넘길 수 있다.

반면 위의 코드는 sum(visitors[:x])를 초기에 한 번만 계산하므로 O(x)이고, 슬라이딩 윈도우로 접근하는 부분도 O(n - x)이므로 시간을 초과하지 않는다.

# 오답(시간 초과)

import sys

n, x = map(int, sys.stdin.readline().split())
visitors = list(map(int, sys.stdin.readline().split()))

visitor_cnt = []
for i in range(n - x + 1):
    visitor_cnt.append(sum(visitors[i:i + x]))

max_visitor = max(visitor_cnt)
if max_visitor == 0:
    print("SAD")
else:
    print(max_visitor)
    print(visitor_cnt.count(max_visitor))