문제
풀이
- 문제 풀이의 핵심은 구간(k)에서의 최대값 중 최소값을 구하는 것
- 밑에 1번 코드로 짜고 장렬히 효율성에서 털림
- 이분탐색을 써야하나 싶었는데 왠지 O(n)에 풀릴 것 같았음
- 결국 검색 후 Monotone Queue 를 찾아내 적용시켜 풀었음
- 본 문제같은 케이스를 "Maximum window sliding" 문제라고 한다고 한다(추가 정보 필요시 키워드로 검색)
- 추후에 모노톤 큐에 대한 내용을 정리하기로 하고 일단 간단하게 풀이를 아래 코드에 작성해 놓음
코드
효율성 틀린 초기 코드
- k개 연속으로 0이 되면 더이상 건널 수 없음에서 착안
- 시간 복잡도는 O(k) * O(len(stones) - k) 인데 stones 길이 최대값은 200,000, k도 마찬가지
- k가 100,000이라 했을 때 가볍게 시간을 초과해버린다.
- 애초에 시간복잡도 계산을 잘못하고 잘못짬
def solution(stones, k):
arr = []
for i in range(len(stones) - k + 1) :
arr.append(max(stones[i:i+k]))
return min(arr)
수정코드, monotonic queue
- 큐를 (위치, 값) 튜플로 관리해줌, 큐는 내림차순으로 정렬됨
- 큐의 맨 앞에 있는 값의 위치가 i - k 란 뜻은 더이상 영향을 미치지 않는다는 뜻(구간 k를 벗어났다는 뜻)이므로 제거해줌
- 큐의 마지막에 담긴 원소의 값(stone)이 현재 stone보다 작다면 지금도 앞으로도 구간에서 최대값이 될 수 없으므로 제거해줌
- 큐에 현재 (위치, 값)을 더해주고 cand 배열에 큐 첫번째 값(최대값)을 추가해줌(구간 최대값)
- 이렇게 풀면 구간 k 를 모두 고려하기 전에 앞에 값들이 cand에 추가되므로
cand[k-1:]에서의 최소값을 구해준다.
from collections import deque
def solution(stones, k):
q = deque()
cand = []
for i, stone in enumerate(stones) :
while q and q[0][0] <= i - k :
q.popleft()
while q and q[-1][1] < stone :
q.pop()
q.append((i, stone))
cand.append(q[0][1])
return min(cand[k-1:])