슬라이딩 윈도우_BOJ #21921: 블로그

문제

찬솔이는 블로그를 시작한 지 벌써 N일이 지났다.

요즘 바빠서 관리를 못 했다가 방문 기록을 봤더니 벌써 누적 방문 수가 6만을 넘었다.

찬솔이는 X일 동안 가장 많이 들어온 방문자 수와 그 기간들을 알고 싶다.

찬솔이를 대신해서 X일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는지 구해주자.

입력

첫째 줄에 블로그를 시작하고 지난 일수 N와 X가 공백으로 구분되어 주어진다.

둘째 줄에는 블로그 시작 1일차부터 N일차까지 하루 방문자 수가 공백으로 구분되어 주어진다.

출력

첫째 줄에 X일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다.

만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다.

 

---

시간 초과 풀이

X일 동안의 조회수 합을 각각 계산하여 sum_view_list에 넣고해당 리스트에서 최대값과 최대값의 갯수를 count했는데 시간초과가 발생하였다.

import sys

def input():
  return sys.stdin.readline().rstrip()

# input: N(블로그 일 수), X(특정 기간) 
# output: 'X일 동안 가장 많이 들어온 방문자 수'와 '해당 기간이 몇 개인지'

# X개씩 합을 계산해서 최대값이 몇개인지 확인
N, X = map(int, input().split())
views = list(map(int, input().split()))

# 기간 내 최대 조회수 
sum_view_list = []
for i in range(N - X + 1):
  sum_view_list.append(sum(views[i:i + X]))

max_view = max(sum_view_list)
cnt = sum_view_list.count(max_view)
 
if max_view == 0:
  print('SAD')
else:
  print(max_view)
  print(cnt)

 

슬라이딩 윈도우는 크기가 고정적인 창문을 옆으로 밀면서 이동한다고 생각하면 된다.
윈도우를 한 칸 옮기면 w-1칸은 겹치므로 이전의 결과를 최대한 응용한다.

매번 합계를 구해주는 부분에서 시간 초과가 발생하는 것으로 보인다.

[i ~ i+X]의 합계를 구한 다음, 다음 구간의 합계에서는 [i]를 빼주고, [i+X+1]을 더해주면 그게 [i+1 ~ i+X+1]의 합계임을 이용

N, X = map(int, input().split())
views = list(map(int, input().split()))

if max(views) == 0:
  print('SAD')
else:
  max_view = sum(views[0:X])
  value = max_view
  cnt = 1
  for i in range(X, N):
    value -= views[i-X]
    value += views[i]
    if value > max_view:
      max_view = value
      cnt = 1
    elif value == max_view:
      cnt += 1

  print(max_view)
  print(cnt)