[백준/21921] 블로그 (Python)

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

 

Difficulty : Silver 3

 

Status : Solved

 

Time : 00:08:59

 

---

 

문제 설명

 

찬솔이는 블로그를 시작한 지 벌써 N일이 지났다.
요즘 바빠서 관리를 못 했다가 방문 기록을 봤더니 벌써 누적 방문 수가 6만을 넘었다.

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

 

 

입력 및 출력

 

입력

 

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

 

출력

 

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

 

입력 예시

 

5 2
1 4 2 5 1

 

출력 예시

 

7
1

 

 

---

 

풀이

 

우리가 원하는 정보는 길이 X의 합이므로, 길이 X의 슬라이딩 원도우를 통해 부분합을 계속해서 구해주면 된다. 즉 O(N)시간 내에 모든 처리가 가능하다.

• 리스트의 슬라이스 메서드는 1회 호출시마다 O(X)의 시간복잡도가 일어나므로, 누적합을 먼저 구하는 식으로 한 번에 슬라이딩 윈도우를 구현하거나 혹은 일일히 업데이트하며 리스트에 추가하는 방식을 사용하도록 하자.

 

 

풀이 코드

import sys
input = sys.stdin.readline

N, X = map(int, input().split())
_num_list = list(map(int,input().split()))
num_list = [ sum(_num_list[:X]) ]

for num1, num2 in zip(_num_list[:N-X], _num_list[X:]) :
  num_list.append(num_list[-1] - num1 + num2)

result = max(num_list)
if result :
  print(result)
  print(num_list.count(result))
else :
  print('SAD')

풀이 완료~