0. 문제

정비사들의 등급을 나타내는 정수 배열 ranks가 주어집니다. ranks[i]는 i번째 정비사의 등급을 나타냅니다.
정비사 등급이 r인 경우, n대의 차를 수리하는 데 걸리는 시간은 r * n² 분입니다.
또한, 수리를 기다리는 자동차의 총 개수를 나타내는 정수 cars가 주어집니다.
모든 정비사는 동시에 수리 작업을 진행할 수 있습니다.

✅ 목표:
모든 자동차를 수리하는 데 걸리는 최소 시간을 반환하세요.

예제 1

• 입력: ranks = [4,2,3,1], cars = 10
• 출력: 16
• 설명

  첫 번째 정비사 (등급 4) → 2대 수리 → 시간: 4 * 2 * 2 = 16
  두 번째 정비사 (등급 2) → 2대 수리 → 시간: 2 * 2 * 2 = 8
  세 번째 정비사 (등급 3) → 2대 수리 → 시간: 3 * 2 * 2 = 12
  네 번째 정비사 (등급 1) → 4대 수리 → 시간: 1 * 4 * 4 = 16
  🚗 최소 16분 내에 모든 자동차를 수리할 수 있음이 증명됨

예제 2

• 입력: ranks = [5,1,8], cars = 6
• 출력: 16
• 설명

  첫 번째 정비사 (등급 5) → 1대 수리 → 시간: 5 * 1 * 1 = 5
  두 번째 정비사 (등급 1) → 4대 수리 → 시간: 1 * 4 * 4 = 16
  세 번째 정비사 (등급 8) → 1대 수리 → 시간: 8 * 1 * 1 = 8
  🚗 최소 16분 내에 모든 자동차를 수리할 수 있음이 증명됨

제약 조건

1 <= ranks.length <= 100,000
1 <= ranks[i] <= 100
1 <= cars <= 1,000,000

---

1. 실패

문제점

• 이진 탐색의 구현은 겉보기에 그럴싸하지만, 정비사의 rank, 자동차의 대수, 정비 시간 사이의 관계를 한꺼번에 다루려고 해서 논리가 불완전함.
• 자동차의 대수를 이진 탐색하면 각 랭크 별로 자동차를 또 분배해야함. 이 경우 연산이 매우 복잡해짐. 너무 많은 경우의 수를 고려해야함.
• 제대로된 반복문 구현이 안됨. 무한 루프 등의 문제 발생.

class Solution {
  public long repairTime(long rank, long cars) {
    return (rank * cars * cars);
  }

  public long repairCars(int[] ranks, int cars) {
    // 각 랭크별로 자동차를 할당. 최적의 자동차 할당 찾아야함.
    // 시간의 미리 정하고 그 안에 가능한지 여부를 판단. 이진탐색 사용
    // 랭크가 작을 수록 많은 차를 정비해야 함.

    long minCars = 1;
    long maxCars = cars;
    long lowestRank = ranks[0];
    long highestRank = ranks[0];

    for (long rank: ranks) {
      if (lowestRank > rank)
        lowestRank = rank;
      if (highestRank < rank)
        highestRank = rank;
    }

    while (minCars < maxCars) {
      long midCars = (minCars + maxCars + 1) / 2;

      if (repairTime(lowestRank, midCars)
          > repairTime(highestRank, (cars - midCars + 1) / (ranks.length - 1)))
        maxCars = midCars;
      else
        minCars = midCars + 1;
    }
    return repairTime(lowestRank, minCars);
  }
}

2. 풀이

핵심 아이디어

$r\times n^2≤mid,\quad n≤\sqrt \frac{mid}{r}$

• 최소 정비시간을 리턴해야 하는 함수인 만큼, 정비 시간을 이진 탐색. 시간의 범위를 조정하면서 최적의 시간을 찾아냄.
• 구하고자 하는 것(최소 정비 시간)을 이진탐색할 것.

정석(최적화)

• 각 랭크 별 사람 수를 배열로 표현해서 랭크 그룹별로 주어진 시간동안 정비할 수 있는 최대 자동차 대수를 계산하는 접근.

class Solution {

  public long repairCars(int[] ranks, int cars) {
    int minRank = ranks[0];
    int maxRank = ranks[0];

    // Find min and max rank dynamically
    for (int rank : ranks) {
      minRank = Math.min(minRank, rank);
      maxRank = Math.max(maxRank, rank);
    }
    // Frequency array to count mechanics with each rank
    int[] freq = new int[maxRank + 1];
    for (int rank : ranks)
      freq[rank]++;

    // Minimum possible time, Maximum possible time
    long low = 1;
    long high = (long)minRank * cars * cars;

    // Perform binary search to find the minimum time required
    while (low < high) {
      long mid = (low + high) / 2;
      long carsRepaired = 0;

      // Calculate the total number of cars that can be repaired in 'mid' time
      for (int rank = 1; rank <= maxRank; rank++) {
        carsRepaired +=
            freq[rank] * (long) Math.sqrt(mid / (long) rank);
      }

      // Adjust the search boundaries based on the number of cars repaired
      if (carsRepaired >= cars) {
        high = mid; // Try to find a smaller time
      } else {
        low = mid + 1; // Need more time
      }
    }

    return low;
  }
}

코드 단순화

• 어차피 maxTime을 설정할거면 굳이 랭크의 크기와 상관없음. car * car가 지수적으로 증가하기 때문.
• 각 랭크의 수를 따로 놓기(freq[])보다 ranks에서 하나씩 순차적으로 참조하면 조금 더 이해하기 쉬움. 대신 시간복잡도는 증가.

class Solution {
  public long repairCars(int[] ranks, int cars) {
    long minTime = 1;
    long maxTime = (long) ranks[0] * cars * cars;

    while (minTime < maxTime) {
      long midTime = (minTime + maxTime) / 2;
      long repairedCars = 0;

      for (int rank: ranks) {
        repairedCars += (long) Math.sqrt(midTime / rank);
      }

      if (repairedCars < cars)
        minTime = midTime + 1;
      else
        maxTime = midTime;
    }
    return minTime;
  }
}