[Python] 백준 21921 블로그

https://www.acmicpc.net/problem/21921

 

 

나의 답 (틀림-시간초과)

import sys

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

li = list(map(int,input().split()))

if sum(li) == 0: # 합이 0인 경우, 조회수도 0이므로. SAD 출
    print("SAD")
    sys.exit()
    
MAX = 0
cnt = 1

for i in range (0,len(li)-X+1): # 범위설정
    value = sum(li[i:X+i])
    
    if MAX < value:
        MAX = value
        cnt=1
    elif MAX == value:
        cnt+=1


print(MAX)
print(cnt)

 

파이썬의 슬라이싱 기능을 이용하여.. sum 함수를 사용하고  각각 구해줬으나. 시간 초과가 났다.

아무래도 범위를 정해두고 합 구하고...범위를 정해두고 합 구하고..하는 과정에서 시간 초과가 난 듯 싶다.

그래서 합 구하는 부분을 슬라이싱 윈도우 기법을 활용해서 했더니 통고 ㅏ . . 

 

 

 

다른 사람 답 - 슬라이싱 윈도우 사용

 

import sys

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

# 첫 번째 윈도우의 합을 계산합니다.
current_sum = sum(li[:X])
MAX = current_sum
cnt = 1

# 슬라이딩 윈도우를 이용하여 나머지 부분의 합을 계산합니다.
for i in range(N - X):
    # 현재 윈도우의 합에서 가장 왼쪽 값을 빼고, 오른쪽에 새로운 값을 더합니다.
    current_sum = current_sum - li[i] + li[i + X]
    
    if MAX < current_sum:
        MAX = current_sum
        cnt = 1
    elif MAX == current_sum:
        cnt += 1

# 모든 숫자의 합이 0인 경우를 처리합니다.
if MAX == 0:
    print("SAD")
    sys.exit()

print(MAX)
print(cnt)

 

처음에 윈도우의 합을 계산하고

슬라이싱 윈도우가 되는 범위는 한 칸씩 오른쪽으로 움직이는 원리니, 

기존의 합에서 맨 첫번째 값을 빼고 새로 들어오는 오른쪽 값을 더해가며 합을 구한다.

이렇게 비교해서 구하다 보면 값을 구할 수 있다.

 

시간을 줄일려고,,, 큰 값 인덱스를 찾고..그런 무모한 짓을 했다.