[백준][슬라이딩 윈도우] - 21921. 블로그

오답

from collections import deque

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

visited = list(map(int,input().split()))
visited = deque(visited)
days = 0

res = []

while visited:
    if len(visited) < x:
        break
    sumQ = 0
    for i in range(x):
        sumQ += visited[i]
    visited.popleft()
    res.append(sumQ)
    

if sum(res) == 0:
    print("SAD")
else:
    print(max(res))
    print(res.count(max(res)))

• 초기 아이디어로는 q로 해당 방문자 수를 담아 x만큼 돌고 맨 앞에 부분을 빼주는 식으로 했는데 이런 식으로 진행하면 더했던 값을 계속 다시 더하고 더해주어야 (중간에 껴있는 값들) 하기 때문에 시간 초과가 났다.
• 이를 해결하기 위해서는 투포인터의 기본적 개념인 해당 조건을 충족했다면 맨 앞에 값만 빼고 맨 뒤에 값만 다시 넣어서 값을 찾아가는 방식을 사용해 문제를 풀어야 한다.

n,x = map(int,input().split())
visited = list(map(int,input().split()))
cnt = 0
res = 0

left = 0
right = 1
sum_days = visited[left]

while left <= right:

    if len(visited[left:]) < x:
        break
    if right - left >= x:
        if sum_days == res:
            cnt += 1
        
        if sum_days > res:
            cnt = 1
            res = sum_days
            
        left += 1
        sum_days -= visited[left]
    else:
        sum_days += visited[right]
        right += 1
        
if res == 0:
    print("SAD")
else:
    print(res)
    print(cnt)

정답

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

if sum(visited) == 0:
    print("SAD")
else:
    sum_data = sum(visited[:x])
    max_sum = sum_data
    max_cnt = 1

    for i in range(x, n):
        sum_data += visited[i]
        sum_data -= visited[i-x]

        if sum_data > max_sum:
            max_sum = sum_data
            max_cnt = 1

        elif sum_data == max_sum:
            max_cnt += 1

    print(max_sum)
    print(max_cnt)

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

cnt = 1
SUM = sum(visited[:x]) #초기값으로 잡고 여기서 시작
MAX = SUM
for i in range(x,n):
    SUM += visited[i]
    SUM -= visited[i - x]

    if MAX < SUM:
        MAX = SUM
        cnt = 1
    elif MAX == SUM:
        cnt += 1

if MAX == 0:
    print("SAD")
else:
    print(MAX)
    print(cnt)

 

풀이

• 해당 x까지를 초기값으로 잡아 더해주고 앞에서는 하나 빼주고 뒤에서 하나 더해줘 값을 비교하는 방식으로 진행한다.
• 이때 최대값이 변경될 땐 cnt 값을 1로 초기화해준다.
• 최대값이 현재 다 더한 값과 같다면 cnt를 1만큼 증가시켜준다