← 전체 회차
A-026● Day 262026.05.30mediumleetcode #853neetcode150

자동차 떼

#array#stack#sorting#monotonic-stack
↗ leetcode #853 · car-fleet
01

문제

· problem
P.026

자동차 떼

↗ leetcode #853

n대의 자동차가 주어진 거리에서 시작하여 목표 거리에 도달하려고 합니다. 두 개의 정수 배열 position과 speed가 주어집니다. 둘 다 길이가 n이며, position[i]는 i번째 자동차의 시작 거리, speed[i]는 i번째 자동차의 시간당 거리 속도입니다. 자동차는 다른 자동차를 추월할 수 없지만, 따라잡은 후 더 느린 자동차의 속도로 나란히 이동할 수 있습니다. 자동차 떼는 단일 자동차 또는 나란히 움직이는 자동차 그룹입니다. 자동차 떼의 속도는 그 안에 있는 모든 자동차 중 최소 속도입니다. 자동차가 목표 거리에서 자동차 떼를 따라잡으면, 그 자동차도 자동차 떼의 일부로 간주됩니다. 목표 지점에 도달하는 자동차 떼의 개수를 반환하세요.

제약
  • · 1 ≤ n ≤ 10⁵
  • · 0 < target ≤ 10⁶
  • · 0 ≤ position[i] < target
  • · All position values are unique
  • · 0 < speed[i] ≤ 10⁶
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
12
[10,8,0,5,3]
[2,4,1,1,3]
3
example 2input → output
10
[3]
[3]
1
example 3input → output
100
[0,2,4]
[4,2,1]
1
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    왜 자동차를 위치 순서로 내림차순 정렬해야 하나요?
  • ☐
    자동차가 떼를 이루는지 판단하는 핵심 지표는 무엇인가요?
  • ☐
    스택에서 요소를 제거하는 조건은 무엇인가요?
  • ☐
    자동차들을 속도 순서로 정렬하면 어떻게 될까요?
  • ☐
    도착 시간이 정확히 같은 두 자동차는 반드시 같은 떼를 이루나요?
  • ☐
    처음 자동차부터 처리하면 어떻게 될까요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 위치와 속도 쌍 생성
○
pair = [(p, s) for p, s in zip(position, speed)]
○
pair = list(zip(position, speed))
○
pair = [(s, p) for p, s in zip(position, speed)]
step 2· 위치 내림차순으로 정렬
○
pair.sort(reverse=True)
○
pair.sort()
○
pair.sort(key=lambda x: x[1], reverse=True)
step 3· 스택 초기화
○
stack = []
○
stack = 0
○
stack = set()
step 4· 도착 시간 계산 및 스택에 추가│ 중첩
○
stack.append((target - p) / s)
○
stack.append(target / s)
○
stack.append((target - p) * s)
step 5· 현재 자동차가 이전 떼에 합류하는지 확인│ 중첩
○
if len(stack) >= 2 and stack[-1] <= stack[-2]:
○
if len(stack) >= 2 and stack[-1] > stack[-2]:
○
if stack[-1] <= stack[-2]:
step 6· 따라잡힌 떼 제거│ │ 중첩
○
stack.pop()
○
stack.pop()
stack.append((target - p) / s)
○
stack.clear()
step 7· 떼의 개수 반환
○
return len(stack)
○
return len(pair)
○
return stack[-1] if stack else 0
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
class Solution:
2
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
3
        pair = [(p, s) for p, s in zip(position, speed)]
4
        pair.sort(reverse=True)
5
        stack = []
6
        for p, s in pair:  # Reverse Sorted Order
7
            stack.append((target - p) / s)
8
            if len(stack) >= 2 and stack[-1] <= stack[-2]:
9
                stack.pop()
10
        return len(stack)
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
12
[10,8,0,5,3]
[2,4,1,1,3]
→
3
case 2
10
[3]
[3]
→
1
case 3
100
[0,2,4]
[4,2,1]
→
1
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.