[BOJ: 21921] - Python / 파이썬 - 블로그

문제

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

시간 복잡도

• 최대 n만큼의 반복 -> $O(n)$
• n의 최대값이 250,000 이므로 충분하다.

문제 접근법

1. 입력 받은 방문자들의 총 합이 0이라면 바로 SAD를 출력하고 종료한다.
2. 처음부터 x번째 까지 방문자의 합을 구한다.
3. 딕셔너리를 정의하고 2번에서 구한 합을 key로 하여 value를 1로 설정한다. (value는 개수)
4. 1번 인덱스부터 x명씩 윈도우 슬라이딩을 한다.
   4-1. 2번에서 구한 합으로부터 시작하여, 왼쪽에 있는 방문자를 빼고 오른쪽에 있는 방문자를 더한다.
   4-2. 4-1에서 계산한 값을 딕셔너리의 key로 하여 value를 1씩 추가한다.
5. 딕셔너리에서 가장 큰 key를 구한다.(합이 가장 큰 경우)
6. 해당 key와 value를 출력한다.

코드

# BOJ
# S3 - 21921(블로그)

import sys
from collections import defaultdict
input = sys.stdin.readline

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

if sum(visitors) == 0:
    print("SAD")
else:
    total = sum(visitors[:x])
    results = defaultdict(int)
    results[total] += 1

    for i in range(1, n - x + 1):
        total = total - visitors[i - 1] + visitors[i + x - 1]
        results[total] += 1

    max_visitors = max(results)

    print(max_visitors)
    print(results[max_visitors])