백준 문제 풀이 - 블로그 21921번

📜 문제 이해하기

찬솔이는 블로그를 시작한 지 벌써 N일이 지났다.
요즘 바빠서 관리를 못 했다가 방문 기록을 봤더니 벌써 누적 방문 수가 6만을 넘었다.
찬솔이는 X일 동안 가장 많이 들어온 방문자 수와 그 기간들을 알고 싶다.
찬솔이를 대신해서 X일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는지 구해주자.

💡 문제 재정의

N일동안의 조회수 나열이 들어올 때 X일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 인지 출력하라.

✏️ 계획 수립

이 문제의 핵심은 이미 구한 합을 다시 구할 필요가 없다는 것이다. 따라서 슬라이딩 윈도우를 만들어 다음에 더할 값을 더하고 필요없는 값을 버리면서 나아간다.
먼저 X - 1번까지 부분합을 구한다. X - 1번부터 값을 더하고 i-X+1번 값을 빼준다. 이 값들을 전부 배열에 넣어주고 max값을 구하고 그 값의 count를 출력하면 된다.

💻 계획 수행

if __name__ == '__main__':
    N, X = map(int, input().split())
    view_counts = list(map(int, input().split()))
    period_view_counts = []
    partial_sum = 0

    for i in range(X - 1):
        partial_sum += view_counts[i]

    for i in range(X - 1, N):
        partial_sum += view_counts[i]
        period_view_counts.append(partial_sum)
        partial_sum -= view_counts[i-X+1]

    max_period_count = max(period_view_counts)
    period_count = period_view_counts.count(max_period_count)

    if max_period_count == 0:
        print("SAD")
    else:
        print(max_period_count)
        print(period_count)

🤔 회고

이 문제는 O(N²)안에 풀 수 있는 쉬운 알고리즘이 있다. 하지만 그 알고리즘을 사용하면 시간 초과가 나기 때문에 O(N) 즉, 선형시간안에 문제를 풀어야한다. 슬라이딩 윈도우 기법을 이용해서 각 부분합을 구함으로써 이 문제를 해결할 수 있었다.