[Python] 21921. 블로그

문제

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

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

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

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

---

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

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

 

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

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

•  1 <= X <= N <= 250,000 
•  0 <= 방문자 수 <= 8,000

풀이

처음에는 for문 안에서 리스트 슬라이싱과 sum()을 활용하여 각 범위의 인원수를 매번 구하고, if-else문을 활용해 최대 인원수를 저장, count를 세는 로직을 짰다. 그런데 시간 초과가 떠버림 ... 알고 보니 이 문제의 데이터 최대 크기는 25만 개인데, 그럼 그만큼 sum()을 호출하는 횟수도 늘어나게 되고 그 결과 시간 초과가 나 버리는 것이었다. 이 문제는 슬라이딩 윈도우 기법을 활용하여 푸는 문제였다. 맨 처음에 첫 번째 구간의 합만 sum()으로 구해놓은 뒤, for문에서는 맨 앞 인덱스 값을 빼고 그 다음 인덱스 값을 더하며 구간 값을 구한다. 

최종 코드

import sys

data = sys.stdin.read().split()
n, x = int(data[0]), int(data[1])
visit = list(map(int, data[2:]))
window = sum(visit[0:x])
high = window
cnt = 1
if sum(visit) == 0:
    print("SAD")
else:
    for i in range(1, n - x + 1):
        window = window - visit[i - 1] + visit[x + i - 1]
        if high < window:
            high = window
            cnt = 1
        elif high == window:
            cnt += 1
    print(high, cnt, sep="\n")

잘 구현되었다. 성능 개선 측면에서 크게 고칠 부분은 없어보이고 우선시하는 성능이 메모리, 속도 등 개인의 선호도 차이에 따라 달라지는 정도인 것 같아서 이번엔 그냥 끝