LeetCode 853 Car Fleet 풀이: 도착 시간을 비교하는 그리디

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

• 문제: 853. Car Fleet
• 출처: LeetCode
• 자체 판단 난이도: Level 3

차량의 초기 위치와 속도만으로 앞 차량에 따라잡히는지 판단해야 함. 단순히 빠른 차량의 수를 세어서는 안 된다. 목적지에 가까운 순서로 차량을 정렬한 뒤 도착 시간을 비교해야하고, 차량이 앞 차량을 추월할 수 없다는 조건을 함께 고려해야함 Level 3으로 판단했다.

1. 문제 요약

같은 목적지로 이동하는 차량들의 position과 speed가 주어진다. 차량은 앞 차량을 추월할 수 없고, 따라잡으면 앞 차량과 같은 속도로 이동하는 하나의 플릿이 된다. 목적지에 도착하는 서로 다른 플릿의 수를 반환한다.

각 차량의 목적지 도착 예정 시간은 다음과 같이 계산할 수 있다.

도착 시간 = (target - position) / speed

중요한 조건은 아래와 같다.

• 차량 수는 1 이상 10^5 이하
• 0 < target <= 10^6
• 모든 차량의 위치는 서로 다르고 0 <= position[i] < target임
• 속도는 1 이상 10^6 이하
• 뒤 차량이 앞 차량을 따라잡아도 추월할 수 없으며, 두 차량은 같은 플릿이 된다.
• 뒤 차량이 플릿과 목적지에 도착하는 순간 만나는 경우에도 같은 플릿으로 처리한다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

그리디 선택 기준

차량을 목적지에 가까운 순서 position을 내림차순으로 정렬한다. 이렇게 하면 현재 차량보다 앞에 있는 차량이나 플릿을 확인한 상태가 된다.

현재 차량의 도착 시간을 current_time, 바로 앞 플릿의 도착 시간을 last_fleet_time이라고 한다.

• current_time <= last_fleet_time: 뒤 차량이 앞 플릿보다 먼저 또는 동시에 도착할 수 있으므로 이동 중 따라잡는다. 새 플릿을 만들지 않음
• current_time > last_fleet_time: 뒤 차량이 앞 플릿에 도착하기 전에 목적지에 도달할 수 없으므로 앞 플릿을 따라잡지 못한다. 새 플릿을 만들고 시간을 갱신

첫 번째 차량은 항상 하나의 플릿을 만들며, 이후 새 플릿이 생길 때마다 개수를 증가시킨다. 실제로 모든 플릿의 시간을 저장할 필요 없이 가장 최근 플릿의 도착 시간만 기억하면 된다.

앞 플릿의 도착 시간이 비교 기준이 되는 이유

위치 내림차순으로 보면 현재 차량 앞에는 이미 플릿이 확정되어 있다. 현재 차량의 도착 시간이 그 플릿보다 빠르거나 같으면 이동 중 따라잡아 하나로 합쳐진다. 더 늦으면 따라잡을 수 없으므로 새 플릿이 된다. 새 플릿이 생긴 경우에만 기준 도착 시간을 갱신한다.

공식 예제의 차량을 목적지에 가까운 순으로 정렬하면 도착 시간은 다음과 같다.

마지막 플릿 하나의 도착 시간만 저장해도 충분하다. 현재 차량이 그 플릿에 합류하면 기준은 그대로이고, 새 플릿을 만들 때만 기준이 바뀐다. 도착 시간이 같은 차량도 목적지에서 만나므로 합쳐야 하며, 새 플릿 조건은 엄격한 current_time > last_fleet_time이다.

시간·공간 복잡도

차량을 위치 기준으로 정렬하는 데 O(n log n) 시간이 걸리고, 정렬된 차량을 한 번 순회하는 데 O(n) 시간이 걸린다. 따라서 전체 시간 복잡도는 O(n log n)이다. 위치와 속도를 묶은 목록을 저장하므로 공간 복잡도는 O(n)이다.

3. 문제 해결 코드 (Python)

먼저 position과 speed를 차량 쌍으로 묶어 위치 내림차순으로 정렬한다. 첫 차량의 도착 시간을 last_fleet_time으로 삼고, 뒤 차량의 시간이 더 클 때만 fleet_count와 기준 시간을 갱신한다.

class Solution:
    def carFleet(self, target: int, position: list[int], speed: list[int]) -> int:
        cars = sorted(zip(position, speed), reverse=True)
        fleet_count = 0
        last_fleet_time = 0.0

        for car_position, car_speed in cars:
            current_time = (target - car_position) / car_speed

            if current_time > last_fleet_time:
                fleet_count += 1
                last_fleet_time = current_time

        return fleet_count

cars를 위치 내림차순으로 정렬하면 같은 위치가 없다는 조건에서 정렬된 순서가 곧 목적지에 가까운 순서가 된다. 현재 시간이 기준 시간보다 작거나 같으면 새 플릿을 만들지 않고, 더 클 때만 새 플릿으로 기록한다. Python의 /는 도착 시간을 실수로 계산하므로 소수 도착 시간도 비교할 수 있다.

4. 오답 접근과 반례

속도가 빠른 차량마다 플릿을 만들기

차량의 속도가 빠르다고 항상 독립 플릿으로 도착하는 것은 아니다. 앞 차량을 따라잡으면 추월할 수 없기 때문에 앞 차량과 같은 플릿이 된다.

target = 10
position = [1, 4]
speed = [3, 2]

위치 1 차량의 도착 시간은 3, 위치 4 차량의 도착 시간은 3이다. 뒤 차량은 앞 차량과 목적지에서 만나므로 정답은 2가 아니라 1이다. 속도 자체가 아니라 앞 플릿과 비교한 도착 시간을 사용해야 한다.

위치를 오름차순으로 처리하기

먼 위치의 차량부터 처리하면 현재 차량이 어느 앞 차량 또는 합쳐진 플릿을 따라잡는지 바로 확정하기 어렵다. 예를 들어 다음 입력에서는 위치 0 차량이 위치 1과 3의 차량을 어떻게 만나는지 앞쪽 플릿이 먼저 정리되어야 한다.

target = 12
position = [10, 8, 0]
speed = [2, 4, 1]

목적지에 가까운 차량부터 처리해야 앞 플릿의 최종 도착 시간을 기준으로 뒤 차량을 판단할 수 있다.

같은 도착 시간을 새 플릿으로 처리하기

current_time < last_fleet_time만 합치는 조건으로 작성하면 목적지에서 동시에 만나는 차량을 분리하게 된다. 문제에서는 도착 순간에 만나는 경우도 같은 플릿이므로 <=를 사용해 합쳐야 한다.

복사해 실행할 테스트

아래 assert를 풀이 코드와 같은 Python 파일에 붙여 실행하면 공식 예제와 도착 시각이 같은 경우를 재현할 수 있다.

solver = Solution()
assert solver.carFleet(10, [4, 1, 0, 7], [2, 2, 1, 1]) == 3
assert solver.carFleet(10, [1, 4], [3, 2]) == 1
assert solver.carFleet(10, [3], [2]) == 1

5. 공식 예제와 추가 검증

작성한 carFleet 함수를 Python으로 실행해 공식 예제와 경계 사례를 확인했다.

공식 예제

추가 검증 1: 차량 한 대

입력: target = 10, position = [3], speed = [2]
기대 출력: 1
확인 결과: 통과
검증 목적: 최소 입력에서 차량 하나가 하나의 플릿이 되는지 확인

추가 검증 2: 모든 차량이 독립적으로 도착

입력: target = 10, position = [0, 2, 4], speed = [1, 1, 1]
기대 출력: 3
확인 결과: 통과
검증 목적: 뒤 차량의 도착 시간이 항상 더 커 새 플릿이 만들어지는지 확인

추가 검증 3: 뒤 차량이 모두 앞 플릿에 합류

입력: target = 10, position = [0, 2, 4], speed = [10, 4, 2]
기대 출력: 1
확인 결과: 통과
검증 목적: 뒤 차량의 도착 시간이 앞 플릿보다 작거나 같을 때 합쳐지는지 확인

추가 검증 4: 목적지에서 정확히 만나는 경우

입력: target = 10, position = [1, 4], speed = [3, 2]
기대 출력: 1
확인 결과: 통과
검증 목적: 도착 시간이 같은 차량을 하나의 플릿으로 처리하는지 확인

6. 다른 풀이 방식 검색 및 비교

• Car Fleet 공식 문제는 추월할 수 없는 차량들이 목적지에 도착하는 플릿 수를 묻는다.
• NeetCode의 Car Fleet 설명은 위치 내림차순 정렬 뒤 스택 또는 마지막 플릿 시간으로 도착 시간을 비교하는 방법을 설명한다.

스택 풀이에서는 지금까지 만들어진 플릿의 도착 시간을 저장하고, 현재 차량이 앞 플릿에 합쳐지면 현재 시간을 스택에서 제거한다. 이 방식은 플릿별 상태를 직접 보여준다는 장점이 있다.

이 글에서는 마지막 플릿의 도착 시간만 유지하는 방식을 사용했다. 차량은 위치 내림차순으로 처리되며 새 플릿이 생기는 순간 기준 시간이 갱신되므로, 스택 전체를 저장하지 않아도 같은 판단을 할 수 있다. 두 방식 모두 정렬 때문에 시간 복잡도는 O(n log n)이다.

마무리

Car Fleet은 차량의 속도 순위를 세는 문제가 아니라 앞 플릿을 따라잡을 수 있는지를 도착 시간으로 판단하는 문제다. 목적지에 가까운 차량부터 정렬하고, 뒤 차량의 도착 시간이 앞 플릿보다 클 때만 새 플릿을 만들면 된다. 같은 도착 시간은 하나의 플릿으로 합치므로 비교 조건은 current_time > last_fleet_time이어야 하며, 전체 시간 복잡도는 O(n log n)이다.