Coding 공부

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

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

if max(arr) == 0:
    print('SAD')
else:
    value = sum(arr[:X])

    max_value = value
    max_cnt = 1

    for i in range(X,N):
        value += arr[i]
        value -= arr[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)        


        

범위 내의 최대 누적자수를 구하면 되는 문제이다.

그래서 나는 슬라이딩 윈도우를 이용해 X의 크기만큼의 첫 방문자수를 구한뒤 한칸씩 이동하면서 더해주고 빼주는 작업을 반복했다.

그리고 값이 갱신되면 1로 초기화를 해주고, 그렇지 않고 최대값과 같은 값이 나왔을때는 더해주는 방식으로 풀 수 있었다.

from collections import defaultdict
from collections import deque
import sys
input = sys.stdin.readline
N, D,K,C = map(int,input().split())
a = defaultdict(int)

sushi = deque()
max_value = 0
# D 초밥의 가짓수
# K 는 연속해서 먹은 초밥의 수
# C 쿠폰번호
sushi_dict = defaultdict(int)
cnt = 0
sushi_list = [int(input()) for _ in range(N)]
for left in range(N+K+1):
    sushi_input = sushi_list[left%N]
    if len(sushi)<K:
        sushi.append(sushi_input)
        if sushi_dict[sushi_input] == 0:
            cnt += 1
        sushi_dict[sushi_input] += 1
        if len(sushi) == K:
            if sushi_dict[C]>0:
                max_value = max(max_value,cnt)
            else:
                max_value = max(max_value,cnt+1)
    else:
        remove_sushi = sushi.popleft()
        sushi_dict[remove_sushi] -= 1
        if sushi_dict[remove_sushi] == 0:
            cnt -= 1
        sushi.append(sushi_input)
        if sushi_dict[sushi_input] == 0:
            cnt += 1
        sushi_dict[sushi_input] += 1
        if sushi_dict[C]>0:
            max_value = max(max_value,cnt)
        else:
            max_value = max(max_value,cnt+1)

print(max_value)

import sys

input = sys.stdin.readline

N = int(input())

arr =[ list(map(int,input().split())) for _ in range(N)]

max_arr = [[0]*3 for _ in range(2)]
min_arr = [[0]*3 for _ in range(2)]

max_arr[0][0] = min_arr[0][0] = arr[0][0]
max_arr[0][1] = min_arr[0][1] = arr[0][1]
max_arr[0][2] = min_arr[0][2] = arr[0][2]

for i in range(1,N):
    max_arr[1][0] = arr[i][0] + max(max_arr[0][0],max_arr[0][1])
    max_arr[1][1] = arr[i][1] + max(max_arr[0][0],max_arr[0][1],max_arr[0][2])
    max_arr[1][2] = arr[i][2] + max(max_arr[0][1],max_arr[0][2])
    min_arr[1][0] = arr[i][0] + min(min_arr[0][0],min_arr[0][1])
    min_arr[1][1] = arr[i][1] + min(min_arr[0][0],min_arr[0][1],min_arr[0][2])
    min_arr[1][2] = arr[i][2] + min(min_arr[0][1],min_arr[0][2])

    for y in range(3):
        max_arr[0][y] = max_arr[1][y]
        min_arr[0][y] = min_arr[1][y]

print(max(max_arr[0]),min(min_arr[0]))

처음 풀어본 슬라이딩 윈도우 관련 문제이다. 들어오는 N의 최대값이 10만이므로, 그대로 전체에 대해서 행렬을 만들경우, 메모리 초과가 날 수 있다.

그럴때 사용하는 알고리즘인 것 같다.

슬라이딩 윈도우에 관련된 설명은 blog.fakecoding.com/archives/algorithm-slidingwindow/ 에서 공부했다.

이 문제도 슬라이딩 윈도우를 통해, 최대값과 최소값을 갱신해주면 되는 문제이다.

일단 한 행에는 3개의 인수가 나와있고, 그 행에서 최대값을 얻을 수 있는 경우는

첫번째 열은 첫번째 열과 값과 그전 행의 첫번째 열과 두번째 열 중 더 큰 값을 더하는 경우이고,

두번째 열은 두번째 열의 값과 그전 행의 첫번째, 두번째, 세번째 열 중  가장 큰 값과 더해주는 것이다.

세번째 열은 세번째 열의 값과 그전 행의 두번쨰,세번째 열 중 가장 큰 값과 더해주는 것이다.

구해진 값들은 현재 행의 각 열에서의 최대값을 구한것이다. 그러면 이 다음행은 이 전전 행 현재행의 그전 행의 값의 유무는 상관이 없다. 현재행의 값들만 알고 있으면 위의 로직을 다음행에서 진행할때에는 전전행은 필요가 없으므로, 현재행에서 구한 값들의 위치를 이전행으로 옮겨주는 과정을 하면 된다.

최소값은 max에서 min으로 바꿔주기만 하면 된다.