(M - 1696. Jump Game VI) PQ, Monotone Queue 테크닉
2021. 6. 12. 01:15
그냥 DP로 접근해서, 각 노드마다 앞 (Bottom-up의 경우; Top-down이면 뒤) K 범위 탐색 : O(NK)
K 범위 탐색 자체를 줄이지 않는 이상, 기타 잡다한 최적화는 효과 없음
그럼 어떻게?
→ 문제를 바꿔서 생각해보자 (환원)
본질은, K 범위 내의 DP 값 중에서 max값만 뽑아내는 것.
딱 Heap 쓰면 될 것 같지 않음?
다만, K범위에서 벗어난 값이 있으면 pop 해줘야 하니, idx랑 같이 저장해서 매번 범위 내인지 체크
PQ 자체가 넣고 빼는데 O(logN)이라, 그래도 O(NlogK) 나옴.
(Sol 3 - Priority Queue)
시간 더 줄이는 방법 존재. push pop이 O(1)인 deque를 써서 PQ처럼 쓰면 됨.
Monotone Queue Technique
https://goldenriver42.tistory.com/135?category=923015
이러면 O(N)만에 가능
'<PS> > [복기 - LeetCode]' 카테고리의 다른 글
(M - 375. Guess Number Higher or Lower II) Minmax (0) | 2021.07.03 |
---|---|
(M - 729. My Calendar I) Case 분류 + Parametric search (0) | 2021.06.12 |
(H - 1383. Max Perf. of a Team) DP? 그리디? (0) | 2021.06.06 |
(H - 968. Binary Tree Cameras) 노드 상태 강제 (제약 추가 전략) (0) | 2021.05.17 |
(H - 174. Dungeon Game) 거꾸로 생각해보는 DP (0) | 2021.05.14 |