[LeetCode] 2594. Minimum Time to Repair Cars (Python)

 

 

난이도: Medium

Problem Description

---

 

You are given an integer array ranks representing the ranks of some mechanics.

ranks_i is the rank of the i^th mechanic.  A mechanic with a rank r can repair n cars in r * n2 minutes.

 

You are also given an integer cars representing the total number of cars waiting in the garage to be repaired.

 

Return the minimum time taken to repair all the cars.

 

Note: All the mechanics can repair the cars simultaneously.

 

Problem Example

---

Example 1:

Input: ranks = [4,2,3,1], cars = 10
Output: 16
Explanation: 
- The first mechanic will repair two cars. The time required is 4 * 2 * 2 = 16 minutes.
- The second mechanic will repair two cars. The time required is 2 * 2 * 2 = 8 minutes.
- The third mechanic will repair two cars. The time required is 3 * 2 * 2 = 12 minutes.
- The fourth mechanic will repair four cars. The time required is 1 * 4 * 4 = 16 minutes.
It can be proved that the cars cannot be repaired in less than 16 minutes.​​​​​

Example 2:

Input: ranks = [5,1,8], cars = 6
Output: 16
Explanation: 
- The first mechanic will repair one car. The time required is 5 * 1 * 1 = 5 minutes.
- The second mechanic will repair four cars. The time required is 1 * 4 * 4 = 16 minutes.
- The third mechanic will repair one car. The time required is 8 * 1 * 1 = 8 minutes.
It can be proved that the cars cannot be repaired in less than 16 minutes.​​​​​

 

Constraints

---

• 1 <= ranks.length <= 105
• 1 <= ranks[i] <= 100
• 1 <= cars <= 106

 

✏️ Solution

---

class Solution:
    def repairCars(self, ranks: List[int], cars: int) -> int:
        left, right = 1, min(ranks) * cars ** 2

        def can_minute(ranks, cars, mid):
            c = 0
            for rank in ranks:
                c += math.isqrt(mid//rank)
                if c >= cars:
                    return True
            return c >= cars

        while left < right:
            mid = (left + right) // 2

            if can_minute(ranks, cars, mid):
                right = mid
            else:
                left = mid + 1

        return right

 

이 문제도 이진탐색을 통해 해결할 수 있었다.

 

요즘들어 나오는 Daily Problem들이 모두 binary search 문제긴 하지만 유형이 다 똑같은 것 같다.

 

left를 1로 설정하고 right를 min(ranks) * cars * cars로 설정한다.

 

right를 min(ranks) * cars * cars로 설정하는 이유는 구할 수 있는 제일 작은 값 중에 제일 큰 값이기 때문이다.

 

이 범위에서 이진 탐색을 통해 ranks의 각 요소가 주어진 시간 내에 수리할 수 있는 차량 수를 계산하고, 목표 차량 수를 충족하는 최소 시간을 찾는다.

 

이는 math.isqrt(mid//ranks[i])를 통해 쉽게 구할 수 있다.

 

예를 들어, ranks = [4,2,3,1], cars = 10, mid = 16이라고 하면 다음과 같이 계산된다.

 

init: c = 0

i = 0: c = c + isqrt(16//4) = 0 + 2 = 2

i = 1: c = c + isqrt(16//2) = 2 + 2 = 4

i = 2: c = c + isqrt(16//3) = 4 + 2 = 6

i = 3: c = c + isqrt(16//1) = 6 + 4 = 10

 

이 때, c = 10이기 때문에 c >= cars를 만족한다.

 

 

각 ranks[i]의 math.isqrt(mid//ranks[i]) 값을 모두 더해 cars보다 크거나 같다면 현재 mid분 만에 모든 차량을 복구할 수 있다고 볼 수 있다.

 

따라서 이를 만족하면 right = mid로 설정해 더 적은 시간안에 모든 차량을 복구할 수 있는 지 확인한다.

 

만약 현재 mid분 만에 모든 차량을 복구할 수 없다면 시간을 더 크게 해줘서 확인해야하기 때문에 left를 mid+1로 설정하여 다시 진행한다.

 

마지막에는 right를 return하고 정답을 맞출 수 있었다.

 

⚙️ Runtime & Memory

---

 

---

문제: 2594. Minimum Time to Repair Cars

 

깃허브: github

algorithmPractice/LeetCode/2665-minimum-time-to-repair-cars at main · laewonJeong/algorithmPractice