[Algorithm] BAEKJOON 21921번: 블로그 (Python)

 

https://www.acmicpc.net/problem/21921

 

문제

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

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

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

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

 

입력

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

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

 

출력

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

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

 

 

 

 

풀이

반복문으로 각 구간마다 구간의 합을 더해서 추가해 나가는 방법은 시간 초과가 나왔고  슬라이딩 윈도우 기법을 사용하여 해결하였다.

 

 

Python 소스 코드

import sys
input = sys.stdin.readline

# 블로그를 시작한 날 수 N과 구간 길이 X 입력
N, X = map(int, input().split())

# 방문자 수 리스트 입력
visitors = list(map(int, input().split()))

# 구간의 시작점과 끝점을 설정하고, 초기 구간의 방문자 수 합을 계산
start = 0
end = X
window_sums = []  # 각 구간의 방문자 수 합을 저장할 리스트
current_sum = 0

# 첫 구간의 방문자 수 합을 계산
for i in range(start, end):
    current_sum += visitors[i]
window_sums.append(current_sum)

# 슬라이딩 윈도우를 사용하여 각 구간의 방문자 수 합을 계산
while end < N:
    current_sum -= visitors[start]  # 이전 구간의 시작점을 제외
    current_sum += visitors[end]    # 새로운 구간의 끝점을 포함
    window_sums.append(current_sum)  # 구간의 합을 리스트에 추가
    start += 1
    end += 1

# 최대 방문자 수가 0인 경우 'SAD' 출력
if max(window_sums) == 0:
    print('SAD')
else:
    # 최대 방문자 수와 해당 구간의 개수를 출력
    print(max(window_sums))
    print(window_sums.count(max(window_sums)))