[백준 21921번] 블로그

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

import sys

# X일 동안 가장 많이 들어온 방문자 수와 기간

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

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

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

input = sys.stdin.readline

visit_counts = list(map(int,input().split()))

# 1. 시간복잡도 O(N^2) 풀이
# answer = 0

# count = 0

# for i, value in enumerate(visit_counts):
#     if 0 <= i+x-1 < n:
#         summary = sum(visit_counts[i:i+x])
#         if answer == summary:
#             count += 1
#         else:
#             answer = max(answer,summary)
#             count = 1

# if answer != 0:
#     print(answer)
#     print(count)
# else:
#     print("SAD")

# 2. 시간복잡도 O(N) 풀이 - 슬라이딩 윈도우

if max(visit_counts) == 0:
    print("SAD")
    exit(0)

value = sum(visit_counts[:x])

max_value = value
max_count = 1

for i in range(x,n):
    value += visit_counts[i]
    value -= visit_counts[i-x]

    if value > max_value:
        max_value = value
        max_count = 1
    elif value == max_value:
        max_count += 1

print(max_value)
print(max_count)

이번 문제는 N일 동안의 방문자 수가 주어졌을 때, 연속 X일간 방문한 횟수의 최댓값을 구하는 문제이다.

이 문제 또한 N과 X의 범위가 최대 10^5 이므로 슬라이딩 윈도우를 활용하면 시간초과 없이 문제를 풀이할 수 있다.

그리고 최대 방문자수가 0인 것처럼 초기에 예외처리할 수 있는 경우라면 미리 처리해주어야 불필요한 연산이 줄어든다는 것을 배웠다.