[Leetcode] 853. Car Fleet_해설, 풀이, 설명

---

안녕하세요, HELLO

 

오늘은 Leetcode 알고리즘 문제 '853. Car Fleet'에 대해서 살펴보고자 합니다.

 

알고리즘 문제, 코드, 해설 그리고 Leetcode에서 제공해 준 solution 순서대로 정리하였습니다.

---

STEP 1. 'Car Fleet' 알고리즘 문제

 

STEP 2. 'Car Fleet' 코드(code)

 

STEP 3. 'Car Fleet' 해설

 

반응형

 

STEP 1. '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.

 

시작 마일 (0)에서 마일 떨어진 곳에 n개의 자동차가 있으며, 목표에 도달하기 위해 이동합니다.

두 개의 정수 배열 위치와 속도가 주어지며 둘 다 길이가 n입니다. 여기서 위치[i]는 i번째 자동차의 시작 마일이고 속도[i]는 i번째 자동차의 속도(시간당 마일)입니다. 자동차는 다른 자동차를 지나갈 수 없지만 느린 자동차의 속도로 따라잡아 옆으로 이동할 수 있습니다.

차량의 속도는 차량에 포함된 모든 차량의 최소 속도입니다. 자동차가 마일 목표에서 자동차 함대를 따라잡는 경우에도 여전히 자동차 일체(fleet)의 일부로 간주됩니다. 목적지에 도착할 자동차 일체의 수를 반환합니다.

 

Constraints:

 

• n == position.length == speed.length
• 1 <= n <= 105
• 0 < target <= 106
• 0 <= position[i] < target
• All the values of position are unique.
• 0 < speed[i] <= 106

 

---

STEP 2. 'Car Fleet' 코드(code)

 

■ Runtime: 147ms Beats 69.86%
■ Memory: 36.13MB Beats 92.92%

 

class Solution:
  def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
    '''
    1. Pair position and speed into list and then order by desending
    2. Stack the estimated reaching time by (target-position)/speed
    3. If further car from target point is faster than nearest car,
      then it will be fleeted.
    4. Loop until end of car numbers.
    '''
    pair = [(p, s) for p, s in zip(position, speed)]
    stack = []

    for p, s in sorted(pair, reverse=True):
      stack.append((target-p)/s)

      # stack[-2] : Nearest from target point 
      # stack[-1] : Further than the Nearest from target point 
      if len(stack) >= 2 and stack[-1] <= stack[-2]:
        stack.pop()

    return len(stack)

---

STEP 3. 'Car Fleet' 해설

 

위치와 속도를 쌍으로 List로 내림차순으로 정렬합니다. 그리고 차량 숫자 쌍으로 반복문을 실행하며, 도착지까지 도달하는 시간을 계산하여 각 값 (target - position) / speed을 stack에 저장합니다

 

계산하고자 하는 바는 최종적으로 도착하는 자동차 일체 (fleet)의 개수를 구하는 것입니다. 이는 종료 지점에 제일 가까운 차량과 비교하여, 먼 위치에서 시작한 차량의 속도가 빨라 둘이 일치하는 지를 검토하면 됩니다.

 

왜냐하면 문제에 조건에 따라 1차선으로 움직이기에, 둘의 위치가 같아지면 하나의 묶음으로 처리하고 속도를 느린 속도로 통일하기 때문입니다. 이로 인해 우리는 종료 지점에 제일 가까운 차량과 비교하여, 속도가 충분히 빠르지 않으면 stack에서 제외합니다. 최종적으로 stack의 개수를 반환하면 자동차 일체 (fleet)의 묶음을 알 수 있습니다.

 

 

■ 마무리

 

오늘은 Leetcode 알고리즘 문제 '853. Car Fleet'에 대해서 알아봤습니다.

좋아요와 댓글 부탁드리며,

오늘 하루도 즐거운 날 되시길 기도하겠습니다 :)

감사합니다.