[BOJ/백준] 21921. 블로그 - 슬라이딩 윈도우 (Python)

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

21921번: 블로그

 

 

문제

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

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

 

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

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

 

 

입력

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

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

 

 

출력

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

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

 

 

 

접근

N일 중 연속으로 X일의 합이 가장 큰 것을 구하는 문제여서

처음에는 이중 for문으로 풀었는데 시간 초과가 났다. 

기간동안의 방문자들을 구하는 시간복잡도 O(x) * 기간의 개수 O(n-x+1) => O(x*n)가 되기 때문이다.

import sys; input = sys.stdin.readline

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

res = []
hop = 0

for i in range(n-x+1):
    for j in range(x):
        hop += day[i+j]
    res.append(hop)
    hop = 0

if max(res) != 0:
    print(max(res))
    print(res.count(max(res))) # 리스트에 max(res) 값이 몇 개 있는지
else:
    print('SAD')

 

 

 

따라서 시간복잡도를 낮출 방법을 생각해야 한다.

모르겠어서 구글링을 하다가, 슬라이딩 윈도우라는 기법을 알게 됐다. 

 

 

슬라이딩 윈도우란?

고정된 일정 범위가 있을 때, 이전의 결과를 최대한 응용하여 다음을 계산하면서 효율을 높이는 기법.

ex. 연속된 5개 숫자의 합

 

고정된 일정 범위를 윈도우라 칭하고 합을 계산해보자.

윈도우를 옆으로 한 칸 옮긴다면 원소의 모든 합을 새로 계산할 필요 없이, 그 전에 구했던 합에서 왼쪽 값을 빼고 오른 쪽 값을 더하면 된다!

 

 

 

 

 

따라서 다시 코드를 짜보면,

import sys; input = sys.stdin.readline

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

if max(day) == 0:
    print('SAD')
    exit(0)

value = sum(day[:x]) # 일단 0번째부터 x번째 전까지 sum
max_value = value
max_cnt = 1

# 슬라이딩 윈도우 (한 칸씩 옆으로 옮겨가며 이전 값 최대한 활용)
for i in range(x, n):
    value += day[i] # 뒤에 값 더해주기
    value -= day[i-x] # 앞에 값 빼주기

    if value > max_value:
        max_value = value
        max_cnt = 1 # 카운트 초기화
    elif value == max_value:
        max_cnt += 1

print(max_value)
print(max_cnt)

 

일단 value에 초기값 (0번째부터 x번째 전까지 합한 값) 넣어주고

max_value를 value로 설정해준다.

 

for문을 돌릴 때 인덱스는 x부터 시작!

현재 초기 윈도우가 0~x까지의 합이니까, 그 윈도우를 한 칸 오른쪽 옆으로 옮긴다고 생각해보자.

뒤의 새로운 값 day[i]를 더해주고, 앞의 값 day[i-x]를 빼주면 되겠지.

 

우리가 구해야 하는 것은 max_value와 그 값이 몇 개 있는지 count 하는 것이므로 !!

현재 value가 max_value보다 큰 경우 max_value 값을 업데이트 해주고 count를 초기화해준다.

또한 현재 value가 max_value와 일치하는 경우 count를 +1 해준다.

 

 

 

시간복잡도를 고려해서 풀이하는 것이 어렵게 느껴진다.

그러나 그리디도 그렇고 슬라이딩 윈도우도 그렇고 비슷한 본질인 것 같다.

최대한 이전 결과를 활용해서 새롭게 추가하는 연산의 수를 줄이는 것!

관련 문제를 더 풀어봐야겠다.