🔒 문제 설명
N개의 수 A1, A2, ..., AN과 L이 주어진다.
Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.
🔓 소스 코드
import sys
from collections import deque
input = sys.stdin.readline
N, L = map(int,(input().rsplit()))
num = list(map(int, input().rsplit()))
D = deque()
for i in range(N):
#슬라이딩 윈도우 범위를 벗어나는 원소 popleft
if D and D[0][0] <= i-L:
D.popleft()
#들어올 원소가 기존의 원소보다 작으면 기존원소 pop
while len(D) >=1 and num[i] < D[-1][1]:
D.pop()
D.append((i, num[i]))
print(D[0][1], end=" ")🔑 해결 방법
처음 문제를 보고 단순하게 start, end해서 min과 max를 사용하면 되지 않을까 생각했지만 시간초과가 발생했고
아무리 생각해도 모르겠어서 어떻게 풀면 좋을지 검색을 하니 슬라이딩 윈도우를 사용하면 될 것 같았다!
슬라이딩 윈도우 범위는 i-L을 기준으로 정답 deque인 D의 범위가 슬라이딩 윈도우를 벗어나지 않도록 하였다.
num[i]가 D의 가장 오른쪽(가장 최근의) 원소의 값보다 작으면 D의 가장 오른쪽 원소를 제거 -> 현재 처리하는 원소보다 큰 값인 기존의 원소를 제거하는 역할
이 문제를 풀면서 슬라이딩 윈도우 개념에 대해 알게 되었고 괜히 플래티넘 문제가 아니었다 ㅎㅎ
