LeetCode 1870. Minimum Speed to Arrive on Time

🗓️ Daily LeetCoding Challenge July, Day 26

(23.07.26) 으아아… bruteforce로 풀었더니 TLE (Time Limit Exceeded)… 그래서 binary-search로 풀어도 여전히 TLE. 하… C++나 Java는 잘만 통과하는거 같은데 ‘[1,1,10000000]’ 같은 예시가 나오면 time complexity가 $ O(10^7) $ 이 되어버려서 파이썬은 삐빅- 실패!를 외친다ㅜㅜ

binary search 이분 탐색 풀이

아래 코드처럼 깔끔하게 풀었는데도 TLE 오류가 떴다. 아무래도 함수 따로 하는 것 조차도 시간 복잡도에 기여하는듯, 한번에 코드를 작성하는 식으로 다시 재구성해보기로 했다.

class Solution:
    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:
        # binary-search
        low,top = 1,10**7
        while low <= top:
            mid = (low+top)//2
            if self.check(dist, hour, mid):
                low = mid -1
            else:
                high = mid+1
        return mid if self.check(dist, hour, mid) else -1
        
    def check(self, dist, hour, speed):
        time = 0
        for num in dist[:-1]:
            time += math.ceil(num/speed)
        time += dist[-1]/speed
        return time <= hour

큰 차이는 아닌거 같지만, 다음과 같이 바꿔보니 통과는 되더라ㅜㅜ 파이썬 TLE 자꾸 걸려서 거슬리네…ㅂㅇㅂ 알고리즘은 맞게 짠거 같은데 시간초과 걸리면 기부니가 매우 좋지 못하다.

import math
class Solution:
    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:
      def can_reach(speed):
        temp = 0
        for i in range(len(dist) - 1):
            temp += math.ceil(dist[i] / speed)
            if temp > hour:
                return False
        return (temp + (dist[-1] / speed)) <= hour

      low = 1
      top = 10**7
      max_speed = -1
      while low <= top:
          mid = (low + top) // 2
          if can_reach(mid):
              max_speed = mid
              top = mid - 1
          else:
              low = mid + 1
      return max_speed