[DSA][Stack] 05. Car Fleet

LeetCode 853

 

05. Car Fleet

There are n cars at given miles away from the starting mile 0, traveling to reach the mile target.
You are given two integer array position and speed, both of length n, where position[i] is the starting mile of the ith car and speed[i] is the speed of the ith car in miles per hour.
A car cannot pass another car, but it can catch up and then travel next to it at the speed of the slower car.
A car fleet is a car or cars driving next to each other. The speed of the car fleet is the minimum speed of any car in the fleet.
If a car catches up to a car fleet at the mile target, it will still be considered as part of the car fleet.
Return the number of car fleets that will arrive at the destination.

 

 

[질문하기]

- 만약 두 차량이 목표 지점에 동시에 도달한다면, 그 두 차량은 하나의 fleet로 간주되나요? 아니면 각자 다른 fleet에 속한다고 봐야 하나요?

 

 

[아이디어]

- stack의 특성을 사용하여 position 기준으로 목적지까지의 시간이 더 오래되는 차량만 count 하자.

 

 

[풀이 1] Stack

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:        
        n = len(position)
        time = []
        for i in range(n):
            time.append([position[i], (target - position[i]) / speed[i]])
        
        time.sort(reverse=True)
        stack = []
        for i in range(n):
            if not stack or time[i][1] > stack[-1]:
                stack.append(time[i][1])
        
        return len(stack)

일직선을 그려서 직접 차량들을 한 칸씩 (각 speed만큼) 움직여보면, position 상 뒤에 있는 차인데 speed가 빠른 경우 추월이 일어난다는 것을 알 수 있다. 따라서 poistion으로 정렬한 후에, target까지의 거리를 speed로 나누어 걸리는 시간을 계산하면 stack의 성질을 이용하여 더 앞에 있는 차이고 걸리는 시간이 크면 fleet를 이루지 않는다는 것을 알 수 있다.

 

⏱️ 시간복잡도

정렬을 하기 때문에 총 시간 복잡도는 O(nlogn)이다.

🧠 공간복잡도

최악의 경우 모든 차 무리들이 stack에 쌓일 수 있으므로 공간 복잡도는 O(n)이다.

 

+) 공간 최적화

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:        
        n = len(position)
        time = []
        for i in range(n):
            time.append([position[i], (target - position[i]) / speed[i]])
        
        time.sort(reverse=True)
        prevTime = time[0][1]
        cnt = 1
        for i in range(1, n):
            if time[i][1] > prevTime:
                cnt += 1
                prevTime = time[i][1]
        
        return cnt

앞에서는 stack의 성질을 잘 보여주기 위해 stack을 사용했지만, 차 무리들을 stack에 기록할 필요가 없기 때문에 stack 상 마지막 차의 목적지까지 걸리는 시간만 변수로 기록하면 공간 사용도 줄일 수 있다.