[Python/파이썬] 백준 21921번 블로그

21921번: 블로그

문제

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

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

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

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

입력

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

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

출력

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

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

코드

• 처음 풀이 코드

import sys
input = sys.stdin.readline

n, x = map(int, input().split())
visitor = list(map(int, input().split()))

max_visitor = 0
cnt = 0

for i in range(n-x+1):
    total = sum(visitor[i:i+x])
    if max_visitor < total:
        max_visitor = total
        cnt = 1
    elif max_visitor == total:
        cnt += 1    
        
if max_visitor == 0:
    print("SAD")
else:
    print(max_visitor)
    print(cnt)

시간 초과로 통과하지 못한 코드이다.

아마 for문 안에서 sum 함수를 사용해서 그런것 같다. 그래서 누적합을 이용하여 합 계산을 1번만 하도록 만들었다.

 

• 정답 코드

import sys
input = sys.stdin.readline

n, x = map(int, input().split())
visitor = list(map(int, input().split()))

if max(visitor) == 0:
    print("SAD")
    exit()
    
acc = [0]
for i in range(n):
    acc.append(acc[i] + visitor[i])

max_visitor = acc[x] - acc[0]
cnt = 1

for i in range(1, n-x+1):
    total = acc[i+x]-acc[i]
    if max_visitor < total:
        max_visitor = total
        cnt = 1
    elif max_visitor == total:
        cnt += 1    

print(max_visitor)
print(cnt)

 

• 방문자 수의 최대값이 0이라면 "SAD"를 출력하고 프로그램 종료
• 누적합을 acc라는 배열에 구한다.
• acc애 저장된 값을 이용해서 1일차부터 시작하여 i ~ i+x일 동안의 방문자 수들 구하여 x일 동안의 최대 방문자 수를 계속 구한다.
  • 이전에 저장된 최대 방문자 수 max_visitor보다 큰 값이 나온다면 max_visitor 값을 갱신해주고 몇 번 나왔는지 저장했던 변수 cnt를 1로 초기화해준다.
  • max_visitor와 같은 값을 갖는 구간이 나오면 cnt를 1 증가시켜준다.