백준 11003[최솟값 찾기]

1. 문제분석 및 접근법

• 최대 범위가 500만으로, 정렬을 사용할 수 없음
• 덱(양쪽으로 값을 넣고 뺄 수 있음)을 사용해야 함

1. 최솟 값 가능성 없는 데이터 삭제

• 새로 들어오려는 수의 바로 앞의 수가 더 크면 바로 삭제

2. 슬라이딩 윈도우 크기 밖 데이터 삭제

• 새로 들어오는 수의 인덱스 번호에서 l을 뺀 값보다 맨 앞의 인덱스 번호가 크거나 같으면 맨 앞 수를 바로 삭제

2. 슈도코드

n, l입력받기
데이터를 담을 덱 생성(mydequeue)
n개의 숫자 입력받아서 리스트에 저장(number)

for i -> n까지:
	덱의 마지막 위치에서 현재 값보다 큰 값이면 제거
    덱의 마지막 위치에 현재 값 저장
    덱의 1번째 위치에서부터 l의 범위를 벗어난 값(now - index-l <= index)을 제거
    덱의 1번째 데이터 출력

3. 코드 구현

	import sys
    from collections import deque
    
    input = sys.stdin.readline
    
    m, l = map(int, input().split())
    mydeque = deque();
    number = list(map(int, input().split()))
    
    for i in range(n):
    	while mydeque and mydeque[-1][0] > number[i]:
        	mydeque.pop()
       	mydeque.append((now[i], i))
        if mydeque[0][1] <= i - l:
        	mydeque.popleft()
        print(mydeque[0][0], end=' ')