백준 21921 : 블로그 (Python)

백준 21921 문제

문제

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

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

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

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

입력

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

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

출력

첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다.

---

나의 풀이

• 이 문제는 슬라이딩 윈도우 알고리즘으로 누적합을 구하는 문제이다. for문에서 sum 내장함수를 사용해 매번 X 크기 배열의 구간 합을 구한다면 시간복잡도가 O(N*X)로 늘어난다. X는 최대 250,000이며 N==X일 수 있기에 시간초과로 통과하지 못할 수 있다. 따라서 첫번째 원소부터 X번째 원소까지의 합을 한 번 구해둔 후 하나의 인덱스씩 이동하며 구간합을 업데이트 해주도록 구현했다.

import sys

N, X = map(int,sys.stdin.readline().split())
visitors = list(map(int,sys.stdin.readline().split()))

total = sum(visitors[:X])
max_num = total 
stack = [total]

for i in range(1,N-X+1):
    temp = total + visitors[X+i-1] - visitors[i-1]
    total = temp
    if max_num < temp:
        max_num = temp
        stack = [temp]
    elif max_num == temp:
        stack.append(temp)
    
if stack[0]!=0:
    print(stack[0],len(stack),sep='\n')
else:
    print("SAD")
    ```