LeetCode 1870, Minimum Speed to Arrive on Time 파이썬, 해설, 풀이
접근
- 가능한 속도 1 과 10^7 사이에서 binary search 로 최소 속도를 찾는다.
- 각 속도마다 train list 를 돌며 걸리는 시간을 계산에서 binary search range 를 조정한다.
- 시간복잡도 O(Nlog10^7)
사고
적정값을 찾아야 되는 문제는 binary search 로 접근하는 경우가 많은거같다. 무난한 binary search 유형이다.
import math
class Solution:
def minSpeedOnTime(self, dist: list[int], hour: float) -> int:
lo, hi = 1, 10000000
minspeed = float('inf')
while hi >= lo:
mid = (hi + lo) // 2
timetook = 0
for i in range(len(dist) - 1):
timetook += math.ceil(dist[i] / mid)
timetook += dist[-1] / mid
if timetook <= hour:
minspeed = mid
hi = mid - 1
else:
lo = mid + 1
if minspeed == float('inf'):
return -1
else:
return minspeed
