[백준 21921번] 블로그 - python

💡문제 분석 요약

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

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

 

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

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

입력

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

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

출력

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

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

💡알고리즘 설계

1. 1일차부터 X일차까지 방문자의 합을 구한다.
2. 방문자의 합이 max_visitors보다 클 경우, 방문자의 합을 max_visitor로 지정하고 기간을 1로 초기화한다.
3. 방문자의 합이 max_visitors와 같을 경우, 기간에 1을 더한다.
4. max_visitors이 0 일 경우 SAD를, 0이 아닐 경우 max_visitors와 기간을 출력한다.

💡코드

N, X = map(int, input().split())
visitors = list(map(int, input().split()))

max_visitors = 0
period = 0

for day in range(N-X):
    if sum(visitors[day:day+X])>max_visitors:
        max_visitors = sum(visitors[day:day+X])
        period = 1
    elif sum(visitors[day:day+X]) == max_visitors:
        period+=1

if max_visitors==0:
    print('SAD')
else:
    print(max_visitors)
    print(period)

시간 초과가 나왔다.

N이 25만인데, X를 sum으로 계산하면 25만번을 계산해야하므로 25만*25만>1억이 나와 시간초과가 된다.

sum을 사용하지 않고, visitors_sum을 임시로 저장하는 방식으로 변경하여 통과했다.

N, X = map(int, input().split())
visitors = list(map(int, input().split()))

visitors_sum = sum(visitors[:X])
max_visitors = visitors_sum
period = 1

for day in range(1, N-X+1):
    visitors_sum = visitors_sum - visitors[day-1] + visitors[day+X-1]
    if visitors_sum>max_visitors:
        max_visitors = visitors_sum
        period = 1
    elif visitors_sum == max_visitors:
        period += 1

if max_visitors==0:
    print('SAD')
else:
    print(max_visitors)
    print(period)

💡시간복잡도

O(N)

💡 느낀점 or 기억할 정보

최적화는 하면 할 수록 익숙해지는 것 같다!