[python3] 2187. Minimum Time to Complete Trips

풀이 일자: 23.03.07

난이도: [Medium]

분류: [Binary Search]

문제 내용

time의 배열의 요소의 개수만큼의 bus가 있고 각각의 bus가 한번 trip을 돌 때의 시간이 각각의 배열 요소가 된다. 버스는 동시에 출발하며 서로 영향을 주지 않고 모든 버스의 trips의 합이 totalTrips이 되는 최소 시간을 구하는 문제이다.

 

문제의 예시를 그대로 든다면,

 

Input: time = [1,2,3], totalTrips = 5

 

Time = 1이면  [1,0,0]번의 Trip을 각각 돌았을 것이기에 totalTrips는 1이 된다

Time = 2이면 [2,1,0]번의 Trip을 각각 돌았을 것이기에 totalTrips는 3이 된다

Time = 3이면 [3,1,1]번의 Trip을 각각 돌았을 것이기에 totalTrips는 5가 된다. => 문제에서 주어진 5에 도달했기에 Stop!

 

 

문제 해결 흐름

1. 그냥 보면 대충 시간을 증가시켜가면서 totalTrips을 구하면 될 것 같다는 생각이 든다.

→ Linear하게 처리를 하면 시간복잡도는 최악의 경우 totalTrips*len(time)만큼의 시간을 가지게 될 것이다.

→ Leetcode에서 이렇게 짜면 TLE가 나올 것은 자명한 사실이다.

 

2. 언제나 Linear한 탐색보다는 Binary한 탐색을 항상 생각해봐야 한다.

→ 주어진 배열은 없지만 현재 구하고 있는 답은 총 totalTrips만큼의 돌 때의 시간을 구하는 거다.

 

3. 그러면 binary Search를 위해 가장 Best Case와 Worst Case를 생각해보자

→ Best Case의 경우 totalTrips가 1 이상이기 때문에 최소 1번으로 totalTrips을 채우는 경우가 될 것이다.

→ Worst Case의 경우 가장 시간이 적게 걸리는 trips을 totalTrips만큼 돌려야 끝나는 경우가 될 것이다.

 

즉, 1 <= times <= trips[0]*totalTrips의 범위 내에서 구하면 된다.

 

4. 일반적인 Binary Search를 사용하면 되지만 세부 조건, 즉 mid에 어떤 값을 넣을지 결정하는 조건을 생각해보자.

→ 우선 mid에 해당하는 시간동안 돌 수 있는 횟수를 구한다. 이후 해당 횟수가 totalTrips와 비교하는 것이 주요 조건이 될 것이다.

 

5. mid에 넣을 실제값 결정

→  만약 해당 시간동안 돌 수 있는 횟수가 totalTrips보다 큰 경우 시간을 너무 많이 잡은 것이므로 right = mid를 넣어 시간을 줄여줘야 한다.

→  만약 해당 시간동안 돌 수 있는 횟수가 totalTrips보다 작은 경우 시간을 너무 적게 잡은 것이므로 left = mid + 1을 넣어 시간을 늘려줘야 한다.

→  만약 해당 시간동안 돌 수 있는 횟수가 totalTrips와 같은 경우 시간을 더 적게 잡아도 되는지 확인해야 하므로 right = mid를 넣어 시간을 줄여봐야 한다.

 

class Solution:
    def minimumTime(self, time: List[int], totalTrips: int) -> int:
        length = len(time);
        time.sort();                        # 최소 시간을 찾아야 하기 때문에 sort 진행
        
        maxT = totalTrips * time[0];        # 최악의 경우는 시간이 적게 걸리는 버스가 totalTrips만큼
        low = 1; high = maxT;              
        
        while(low < high):
            mid = low + (high - low) // 2;
            total = 0;

            for i in range(length):         # 각각의 time을 나눠서 총 tour 횟수를 계산
                total += (mid // time[i]);   
            
            if total >= totalTrips:   # 너무 많이 돌거나 같으면 시간을 너무 많이 잡은거
                high = mid;
            else:                    # totalTrips을 넘지 못하는 경우 시간을 적게 잡은거.
                low = mid + 1;

        return low;

=> 이진탐색을 떠올려서 작성한 코드

 

 

Time Complexity: O(NLogM)

이진탐색을 진행하기에 1과 최대 걸리는 시간M의 Log값과 내부에서 실제 걸리는 시간을 계산하기 위한 과정으로 인하여 NLogM정도의 시간복잡도를 가지게 될 것이다.

 

Space Complexity: O(1)

일반적인 변수를 제외하고 어떤 자료구조를 문제풀이에 사용하지 않았기 때문에 1의 공간복잡도를 가지게 될 것이다.

 

 

다른 해결 방식

Binary Search라는 Idea를 떠올릴 수 있다면 쉽게 풀 수 있었던 문제로 Offical Solution이나 User Solution과의 차이는 없었다.

 

 

문제 링크

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

Minimum Time to Complete Trips - LeetCode