[코테연습] 2594. Minimum Time to Repair Cars

https://leetcode.com/problems/minimum-time-to-repair-cars/description/?envType=daily-question&envId=2025-03-16

 

 

1️⃣ 문제 타입

• 이진 탐색 (Binary Search) + 수학적 최적화
• 그리디 알고리즘 (Greedy Approach)
• 정비사별로 자동차 수리 속도가 다르므로 최소 시간을 최적화해야 함.
• 특정 시간 내에 주어진 cars 개를 수리할 수 있는지를 판단하는 **결정 문제(Decision Problem)**로 변환 가능.

---

2️⃣ 문제 분석

• ranks[i]는 i번 정비사의 숙련도를 나타내며, rank가 낮을수록 더 빠르게 수리할 수 있음.
• 정비사가 t초 동안 수리할 수 있는 차량 수는 공식적으로:floor(t/r)\text{floor}(\sqrt{t / r})floor(t/r​)
  • 예를 들어, rank[i] = 4이고 t = 16이면:
    • 16/4=4=2\sqrt{16 / 4} = \sqrt{4} = 216/4​=4​=2 대 수리 가능.
• 목표는 모든 차량을 수리하는 데 필요한 최소 시간을 찾는 것.
• 이진 탐색을 적용할 수 있는 이유:
  • 시간이 길어질수록 더 많은 차량을 수리할 수 있음 (단조 증가 특성).
  • 특정 시간 t에서 cars 개 이상을 수리할 수 있는지 확인하면, t 값을 줄여 최적해를 찾을 수 있음.

---

3️⃣ 문제 풀이

✔ Step 1: 이진 탐색 범위 설정

• 최소 시간 (left): 1초
• 최대 시간 (right): max(ranks) * cars^2 (가장 느린 정비사가 모든 차량을 혼자 수리하는 경우)
• mid = (left + right) // 2를 기준으로 가능한지 확인

✔ Step 2: 특정 시간 mid 내에 cars대 수리 가능한지 체크 (isPossible 함수)

• 각 정비사가 mid 시간 동안 수리할 수 있는 차량 수를 계산하고 총합이 cars 이상인지 확인
• 가능하면 right = mid, 불가능하면 left = mid + 1

✔ Step 3: 이진 탐색 종료 후 최소 시간 반환

• 최적의 시간을 left 값으로 반환

 

> java 

 

class Solution {
    public long repairCars(int[] ranks, int cars) {
        
        long left = 0;
        long right = (long) Arrays.stream(ranks).max().getAsInt() * cars * cars;

        while (left < right) {
            long mid = left + (right - left) / 2;
            if (isPossible(ranks, cars, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    boolean isPossible (int[] rank, int cars, long mid) {

        long total = 0;
        for (int i = 0; i < rank.length; i++) {
            long car = (long) Math.sqrt(mid / rank[i]);
            total+=car;
            if (total >= cars) {
                return true;
            }
        }
        return false;
    }
}

 

 

> python3

 

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

        while left < right :
            mid = left + (right - left) // 2
            if self.isPossible(ranks, cars, mid) :
                right = mid
            else :
                left = mid + 1
        
        return left

    def isPossible(self, ranks, cars, mid) :
        total = 0
        for rank in ranks :
            total += floor(sqrt(mid // rank))
            if total >= cars :
                return True
        
        return False