징검다리 건너기

from math import inf from collections import deque def solution(stones, k): # 배열 내의 k개의 연속된 자연수의 최댓값의 최솟값을 구하는 문제. # # O(n)개의 sliding window 내의 최댓값을 단순히 max()로 구하면 # 당연히 시간초과가 난다. # sliding window 내의 최댓값을 빠르게 구하는 방법이 필요하다. # 세그먼트 트리 써서 O(n x logn) 으로 풀 수도 있을 것 같은데, 해보자. # --> 세그먼트 트리도 시간초과가 난다. 그렇다면 O(n)에 하길 원하는 것 같다. # # 관리해야할 자료구조를 생각해보자. window 내의 maximum 값을 추적할 수 있어야 하고 # window가 해당 값을 이탈하면 그 maximum 값을 삭제하고, 다음 maximum 값을 불러올 수 있어야 한다. # index 값들을 저장한 list (q) 하나를 가지고 이를 구현한다고 생각해보자. # 1. q 내의 인덱스 i에 대해 A[i]는 항상 내림차순으로 정렬되도록 i가 배열되어 있다. # ---> 즉, q[0]은 해당 window의 최댓값의 index이다. # 2. 새로운 인덱스 i를 본다고 하자. 그럼 현재 window는 i-k+1 ~ i 일 것. # 따라서 q[0]이 i-k+1보다 작으면 popleft해서 제거해야 한다. # 3. 또한 새로운 인덱스 i에 대해서 A[i]보다 작은 q[j]들을 pop해서 제거한 뒤 i를 # q에 append한다. # 따라서 popleft, append, pop이 O(1)이면 좋으므로, deque를 쓰자. q, mn, i = deque(), inf, 0 while i < len(stones): if len(q) > 0 and q[0] < i-k+1: q.popleft() while len(q) > 0 and stones[q[-1]] < stones[i]: q.pop() q.append(i) # 이제 stones[q[0]]은 i~i+k window의 최댓값을 가진다. # 적어도 k개의 숫자는 봐야 하므로, i가 k-1 이상일때부터 판단하면 된다. if i >= k-1 and stones[q[0]] < mn: mn = stones[q[0]] i += 1 return mn