[백준] 11003번 최솟값 찾기 Python 해설

출처 : https://www.acmicpc.net/problem/11003

11003번: 최솟값 찾기

슬라이딩 윈도우 알고리즘으로 분류된 문제이다.

열몇 번의 시도만에 풀었다..

 

풀이

---

- Python 정답 코드

from collections import deque

n, l = map(int, input().split())
arr = [*map(int, input().split())]
m = deque()
for i in range(n):
    tmp = arr[i]

    while m and m[-1] > tmp: m.pop()
    m.append(tmp)

    #윈도우 크기보다 커진 단계에서 arr와 비교한 후 left pop
    if i >= l and m[0] == arr[i - l]: m.popleft()
    print(m[0], end=' ')

입력으로 주어지는 모든 값을 배열에 넣어준 뒤 슬라이딩 윈도우 알고리즘을 수행한다.

이상하게 다른 언어로는 맞았던 알고리즘도 안 되서 고생을 많이 했다.

popleft와 pop을 사용하여 시간 복잡도를 줄이고, min함수를 사용하지 않고 필요한 만큼의 비교만 수행하여 시간 복잡도를 최대한 줄인 풀이 방법이다.

 

결과 인증

---

 

부끄럽지만.. 꼭 풀고 싶어서 더 욕심냈던 문제이다..