[백준/21921] 블로그 - 파이썬(Python)

문제

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

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

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

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

입력

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

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

출력

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

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

제한

•  1≤X≤N≤250,000$1 \le X \le N \le 250,000$ 
•  0≤$0 \le$ 방문자 수 ≤8,000$\le 8,000$ 

21921번: 블로그

 

문제 풀이

슬라이딩 윈도우 기법*을 이용하여 문제를 풀 수 있다.

슬라이딩 윈도우 기법이란 ?

슬라이딩 윈도우 알고리즘은 투 포인터 알고리즘과 비슷하나 범위의 제한이 있다는 점에서 다르다. 슬라이딩 윈도우의 경우 특정 범위를 제한하여 이동하는 특징이 있으며 창문을 옆으로 미는 것과 비슷하여 슬라이딩 윈도우 기법이라고 불리는 것 같다.

처음에는 for문에서 계속해서 슬라이싱을 해서 시간 초과가 발생했다. 1일 차부터 X일동안 방문자 수를 더한 후 양 끝 값을 더해주고 빼면서 확인하면 된다. 그리고 최댓값과 값이 같을 경우 횟수를 증가시켜 답을 구했다.

 

import sys
input = sys.stdin.readline

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

tmp = sum(visitors[:X])
max_v = tmp
cnt = 1
for l in range(X, N):
    tmp -= visitors[l - X]
    tmp += visitors[l]
    if max_v < tmp:
        max_v = tmp
        cnt = 1
    elif max_v == tmp:
        cnt += 1
print("SAD") if max_v == 0 else print(max_v, cnt)