[Python] 백준 11003. 최솟값 찾기

11003번: 최솟값 찾기

슬라이딩 윈도우 문제.

 

매번 윈도우 위치를 변경할 때마다 min함수를 사용할 경우, 시간복잡도가 O(n**2)가 된다.

deque를 활용해 삽입/삭제를 빠르게 수행하되,

deque에 값을 저장하는 방식을 약간 변경하면 효율적으로 연산을 수행할 수 있다.

 

아래 풀이에서 더 상세한 해설을 볼 수 있다.

백준 11003번 문제 (최솟값 찾기) with Java · 쾌락코딩

 

	import sys
	from collections import deque
	n, l = map(int, sys.stdin.readline().split())
	arr = list(map(int, sys.stdin.readline().split()))
	d = [0 for _ in range(n)]
	window = deque()
	for idx in range(n):
	# window의 마지막 값보다 input으로 넣을 값이 작은 경우
	# 최솟값은 어차피 input값이 될 것이므로, window에 굳이 넣을 필요가 없다
	while window and window[-1][1] > arr[idx]:
	window.pop()
	# window 최솟값의 index가 현재 window 크기를 벗어난 경우
	# 값을 빼 준다.
	while window and idx - window[0][0] >= l:
	window.popleft()
	window.append((idx, arr[idx]))
	d[idx] = window[0][1]
	print(*d)

view raw [백준] 최솟값 찾기.py hosted with ❤ by GitHub