백준 21921: 블로그 - 누적 합, 슬라이딩 윈도우(파이썬)

블로그 성공

21921번: 블로그

문제

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

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

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

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

입력

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

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

출력

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

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

제한

1 <= X <= N <= 250,000

0 <= 방문자 수 <= 8,000

 

내 코드

import sys
n,x=map(int,sys.stdin.readline().split())
arr=list(map(int,sys.stdin.readline().split()))

#숫자들 중에서 가장 큰 값이 0이면 SAD이다.
isSAD=False
if max(arr)==0:
    isSAD=True


base_arr=arr[0:x] #가장 최초의 탐색 구간은 [0:x]이다.
max_sum=sum(base_arr) #최대 합을 sum(base_arr)로 초기 세팅.

tmp_sum=max_sum #가장 최초의 최대 값을 세팅하고 최대값 찾기 시작
for i in range(n-x):
    tmp_sum-=arr[i] #구간이 이동할 때 빠지는놈 빼기.
    tmp_sum+=arr[i+x] #구간이 이동할 때 들어오는놈 더하기.
    max_sum=max(max_sum,tmp_sum) #기존의 최대랑 현재 값이랑 크기 비교.


#위의 과정에서 max_sum에 최대합이 담겨있다 ㅇㅇ

cnt=0
tmp_sum=sum(base_arr)
if max_sum==tmp_sum: #첫 구간 먼저 처리
    cnt+=1

#위의 과정과 완전 동일한데, max_sum과 같은 애가 나오면 cnt++;
for i in range(n-x):
    tmp_sum-=arr[i]
    tmp_sum+=arr[i+x]

    if tmp_sum==max_sum:
        cnt+=1

#정답 출력
if isSAD:
    print("SAD")
else:
    print(max_sum)
    print(cnt)

풀이 및 접근)

- 문제에서 구간의 합을 구하는 것을 알 수 있었고, 그 구간의 길이가 고정된 것임을 파악했다. 여기에서 바로 슬라이딩 윈도우 알고리즘을 써야함을 알 수 있다.

- 내 코드에서는 우선 최대 합을 구하고, 다시 for문을 돌면서 그 최대 합과 같은 합일 때를 카운트 하는 식으로 구했다.

- 하지만 더 최적화된 코드가 있어 그 코드 또한 참고해 보았다.

 

 

최적화 된 코드

import sys
n,x=map(int,sys.stdin.readline().split())
arr=list(map(int,sys.stdin.readline().split()))

if max(arr)==0: #SAD 처리.
    print("SAD")
else:
    max_sum=sum(arr[0:x]) #최대합 초기 세팅.
    tmp_sum=max_sum #tmp_sum을 초기 최대합으로 초기 세팅.
    cnt=1 #적어도 cnt는 1개 이상.

    for i in range(n-x):
        tmp_sum-=arr[i] #구간 이동에 따라 빠지는 놈,
        tmp_sum+=arr[i+x] #더해지는 놈.

        if tmp_sum>max_sum: #현재 합이 기존 최대합보다 크면,
            max_sum=tmp_sum #최대합을 현재껄로 업데이트.
            cnt=1 #최대합이 업데이트 됐으므로, cnt를 다시 1 초기화.
        elif tmp_sum==max_sum: #현재 합이 기존 최대합이랑 같으면,
            cnt+=1 #cnt++;
    
    #답 출력.
    print(max_sum)
    print(cnt)

*참고한 블로그

https://cheongyastory.tistory.com/175

[백준] 블로그 - 21921번 문제 (Python)