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