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