[Coding Test][Python][백준] BOJ #21921 블로그

문제)

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

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

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

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

입력)

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

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

• $1 \le X \le N \le 250,000$ 
• $0 \le$ 방문자 수 $\le 8,000$ 

출력)

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

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

---

풀이)

※ 풀이 아이디어

고정된 크기의 Sliding Window를 적용하여 X일 동안의 방문자 수 구하기
1. 첫 번째 X일 동안의 방문자 수 구하기
2. 한칸 씩 이동하며 방문자수를 갱신하고 max 값과 비교

 

N, X = map(int, input().split())
# 방문자 수
visitors = list(map(int, input().split()))

# 최대 방문자 수, 최대 방문자 기간 일수
max_visitor, max_visitor_count = sum(visitors[0:X]), 1
range_sum = max_visitor

if max(visitors) == 0:
    print("SAD")
else:
    for i in range(X, N):
        range_sum -= visitors[i-X] 
        range_sum += visitors[i]

        if  range_sum > max_visitor:
            max_visitor = range_sum
            max_visitor_count = 1
        elif range_sum == max_visitor:
            max_visitor_count += 1
            
    print(f"{max_visitor}\n{max_visitor_count}")

---

※ 처음 풀이

for i in range(N):
    start = i
    end = i + X 

    if end >= N:
        break

    range_sum = sum(visitors[start:end])
    
    if  range_sum > max_visitor:
        max_visitor = range_sum
        max_visitor_count = 0
    elif range_sum == max_visitor:
        max_visitor_count += 1

처음에는 가볍게 start와 end를 두고 한칸씩 이동해가며 range_sum을 구하였다.
하지만 시간 초과가 났고 원인을 찾는데 꽤 애를 먹었다.
그래서 GPT의 도움을 받아 원인을 물어보니 sum(visitors[start:end])로 부분 합을 구할 때 Indexing을 통해 array에 접근하게 되어 최악의 경우 $O(N^2)$이 나올 수 있다는 것이었다.
그래서 위와 같이 Window 크기만큼 이동하면서 하나씩 더해주고 빼주는 과정을 통해 시간초과를 해결할 수 있게 되었다.