Daily LeetCode Challenge - 2187. Minimum Time to Complete Trips

Problem From.

https://leetcode.com/problems/minimum-time-to-complete-trips/

오늘 문제는 각각의 버스가 한번의 여행을 하는데 걸리는 시간이 담긴 배열 time 을 통해 모든 버스가 최소 한번씩 여행을 하여 totalTrips 를 넘는 최소의 시간을 반환하는 문제였다.

이 문제는 이진탐색으로 풀 수 있는데,
먼저 최소의 시간을 0 최대의 시간을 totalTrips * time[0] 으로 잡는다.
(모든 버스가 최소한 한번 여행을 하게 하기 위함)
그리고 이진탐색을 이용하여, 중간값인 mid 를 구하여, 그 mid 를 time 의 각각의 시간으로 나눈 합이 totalTrips 보다 큰 수 인지 본다.

만약 큰 수라면, 더 줄어들 수 있는 가능성이 있기 때문에, 최대의 시간을 다시 mid 로 잡는다. 만약 작은 수라면, 최소 시간을 늘려야하기 때문에, 최소의 시간을 mid+1 로 잡고 다시 이진탐색을 시작한다.

class Solution {
    fun minimumTime(time: IntArray, totalTrips: Int): Long {
        var min = 0L
        var max = totalTrips.toLong() * time[0]
        while(min < max) {
            val mid = min + (max - min) / 2
            val total = time.map { mid / it }.sum()
            if(total >= totalTrips) max = mid
            else min = mid + 1
        }
        return min
    }
}