[BOJ/py] 21921 블로그

문제 링크 https://www.acmicpc.net/problem/21921

📝 문제

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

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

💻 코드

import sys
input = sys.stdin.readline

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

if max(visitor) == 0:
    print('SAD')
else:
    max_visitor = sum(visitor[:X])
    total = max_visitor
    cnt = 1

    for i in range(X, N):
        total += visitor[i] - visitor[i-X]

        if total > max_visitor:
            max_visitor = total
            cnt = 1
        elif total == max_visitor:
            cnt += 1

    print(max_visitor)
    print(cnt)

📌 해결방법

1. 이중 for문으로 처리하면 시간초과.....!

   처음에는 이렇게 했는데 진짜 계속 시간초과...^^

   for i in range(N-M+1):
       total = 0
       for j in range(i, i+M):
           total += visitor[j]

2. 슬라이딩 윈도우를 사용하여 문제 풀기

   겹쳐지는 부분을 제외한 i-X는 빼주고, i는 더해주는 방식

       for i in range(X, N):
           total -= visitor[i-X]
           total += visitor[i]

💡 배운 점

- 슬라이딩 윈도우

• N개의 원소를 갖는 배열이 존재하고, W개의 창문을 가지고 있다면
• 창문을 왼쪽부터 시작하여 한 칸씩 오른쪽으로 이동함
  (정리 : https://velog.io/@lasteah22/Python-슬라이딩-윈도우)

---

✔ 느낀 점

이런 문제는 항상 이중 for문으로만 처리했던 것 같다; 슬라이딩 윈도우 처음 들어봄...;;; 알고리즘의 세계는 너무 넓고 복잡함........😣