Skip to main content

[11003] problem_title

링크 : https://www.acmicpc.net/problem/11003

1. 문제 분석​

접근 방식: 아이디어 요약

시간 복잡도: O(N)O(N)

2. Python 풀이​

테스트케이스는 맞았지만, 당연히 시간 초과

시간초과

import sys
input = sys.stdin.readline

n,l = map(int, input().split())
A = list(map(int, input().split()))

D=[0]*n
for i in range(n):
    start_index= max(0,i-l+1)
    end_index=i
    D[i]=min(A[start_index:end_index+1])

for d in D:
    print(d, end=' ')

이 문제를 해결하려면 **"deque"**을 알아야 함

핵심 아이디어​

[1]최솟값 가능성이 존재하지 않는 데이터를 삭제하는 것​

슬라이딩 윈도우 형태로 해당 영역에서 최솟값을 찾는데, A[i]<=A[j]A[i]<=A[j]

[2] window 크기 밖에 있는 데이터를 삭제해야함​

deque

3. 학습 내용​

새로 알게 된 점:

4. 관련 개념​

Tags