https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/
Capacity To Ship Packages Within D Days - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
class Solution:
def shipWithinDays(self, weights, D):
left, right = max(weights), sum(weights)
while left < right:
mid, need, cur = (left + right) // 2, 1, 0
for w in weights:
if cur + w > mid:
need += 1
cur = 0
cur += w
if need > D: left = mid + 1
else: right = mid
return left하루에 옮길 수 있는 양을 고정시켜놓고 가능한지 불가능한지 검사한다.
이걸로 이진 탐색을 하면 된다.
하루에 옮길 수 있는 양은 최소 max(weights)여야 하고 최대 sum(weights)까지 가능하다.
가능 여부를 조사하는데 O(N)이 걸리고 이진 탐색을 하는데에 O(log N)이 걸리므로 곱하면 O(N log N)
'코딩 테스트 및 알고리즘 > leetcode for google' 카테고리의 다른 글
| leetcode medium : Number of Subarrays With LCM Equal to K (0) | 2022.11.17 |
|---|---|
| leetcode medium: Implement Trie (Prefix Tree) (0) | 2022.11.16 |
| leetcode medium : Range Sum Query Mutable (1) | 2022.11.15 |
| leetcode hard : Height of Binary Tree After Subtree Removal Queries (0) | 2022.11.04 |
| leetcode medium : Minimum Addition to Make Integer Beautiful (0) | 2022.11.04 |