Car Fleet

Q: Car Fleet의 시간 복잡도는 얼마인가요?

위치 기준 정렬에는 O(n log n) 이 걸리고 스택을 사용하는 순회에는 O(n) 이 걸리므로, 총 시간 복잡도는 O(n log n) 이고 메모리 복잡도는 O(n) 입니다. 모든 자동차를 앞에 있는 모든 자동차와 비교하면 O(n²) 이 걸립니다.

Q: 부동 소수점 없이 도착 시간을 어떻게 비교하나요?

도착 시간은 dist / speed 입니다. 속도는 양수이므로, d1 / s1 > d2 / s2 는 d1 × s2 > d2 × s1 일 때와 정확히 같습니다. 양변은 최대 10^12 의 정수이므로, 64비트 타입으로 계산하면 반올림을 고려할 필요 없이 정확하게 비교할 수 있습니다.

보통스택 정렬

+10

자동차들이 단일 차선 도로를 따라 마일 target을 향해 달립니다. 자동차 i는 마일 position[i]에서 출발하며 시속 speed[i]마일로 달립니다. 어떤 자동차도 다른 자동차를 추월할 수 없습니다. 느린 자동차를 따라잡은 자동차는 그 바로 뒤에 머물고, 그때부터 두 자동차는 더 느린 속도로 하나의 차량 대열처럼 함께 움직입니다.

함수

carFleet(target: integer, position: integer-array, speed: integer-array) → integer

targetinteger: 모든 자동차가 향하고 있는 마일
positioninteger-array: 각 자동차의 시작 마일
speedinteger-array: 각 자동차의 속도(시간당 마일)
반환값integer: 목적지에 도달하는 함대의 수

제약 조건

n == position.length == speed.length
1 ≤ n ≤ 10⁴
1 ≤ target ≤ 10⁶
0 ≤ position[i] < target
1 ≤ speed[i] ≤ 10⁶
모든 위치가 다릅니다.

예제

입력: target = 20position = [14, 2, 8, 17, 0]speed = [3, 6, 4, 1, 2]
출력: 2
설명: 단독으로 이동할 경우 17, 14, 8, 2마일 지점의 자동차는 각각 3, 2, 3, 3시간이 필요하므로, 14마일 지점의 자동차가 17마일 지점의 자동차를 따라잡고 나머지 두 대는 20마일 지점에서 이들을 따라잡습니다. 0마일 지점의 자동차는 10시간이 필요하며 혼자 도착합니다.

입력: target = 9position = [0, 4, 7]speed = [1, 2, 3]
출력: 3
설명: 마일 7, 4, 0 지점에 있는 자동차는 각각 2/3시간, 5/2시간, 9시간이 필요합니다. 각 자동차는 앞차보다 늦게 도착하므로, 아무도 다른 차를 따라잡지 못합니다: 3개의 차량 대열.

후속 질문

위치는 target보다 작은 정수입니다. 비교 정렬 없이 O(n + target) 시간에 차량 대수를 셀 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

하나의 차선에서는 자동차의 순서가 바뀌지 않으며, 모든 것을 결정하는 것은 각 자동차가 혼자 도착할 때 걸리는 시간입니다: (target - position[i]) / speed[i]. 목적지에서 가장 가까운 자동차부터 역순으로 살펴보세요. 자동차는 앞에 있는 차량 무리보다 엄격히 더 늦게 도착할 때만 새로운 차량 무리를 시작합니다.

앞에 있는 모든 차를 확인하세요

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

어떤 차 앞에 있는 모든 차가 혼자 도착할 때 엄밀히 더 일찍 도착하는 경우에만 그 차는 선두 차량입니다. 앞에 있는 차 중 더 일찍 도착하지 않는 차가 있으면, 목적지에 도착하기 전에 내 차가 그 차 또는 그 차의 차량 무리를 따라잡습니다. 모든 차가 더 일찍 도착한다면, 차량 무리는 소속 차량 중 가장 늦게 혼자 도착하는 시간에 도착하므로 앞의 어떤 차도 내 차를 지체시킬 수 없습니다. 도착 시간을 교차 곱셈으로 정확히 비교하면서 선두 차량의 수를 세세요.

각 차는 n개의 차를 모두 살펴봅니다. n = 10^4일 때 확인 횟수는 10^8입니다.

알고리즘

fleets = 0으로 설정합니다.
각 자동차 i에 대해 position[j] > position[i]인 모든 자동차 j를 살펴봅니다.
어떤 j가 (target - position[j]) × speed[i] ≥ (target - position[i]) × speed[j]를 만족하면 자동차 i는 따라잡힌 것이므로 건너뜁니다.
그렇지 않으면 자동차 i가 차량 무리를 이끕니다. fleets에 1을 더합니다.
fleets를 반환합니다.

def carFleet(target, position, speed):
    n = len(position)
    fleets = 0
    for i in range(n):
        dist = target - position[i]
        caught = False
        for j in range(n):
            # Car j is ahead and would not arrive before car i: car i catches it.
            # (target - position[j]) / speed[j] >= dist / speed[i], without division.
            if position[j] > position[i] and (target - position[j]) * speed[i] >= dist * speed[j]:
                caught = True
                break
        if not caught:
            fleets += 1
    return fleets

위치별로 정렬하고 함대를 쌓으세요

핵심 아이디어

목적지에 가까운 순서대로 정렬하면, 현재 차량보다 앞에 있는 차량은 이미 확인한 차량, 즉 이미 대열에 포함된 차량뿐입니다. 대열을 스택에 저장하고, 각 대열은 맨 앞 차량의 거리와 속도로 저장합니다. 맨 앞 차량이 대열의 도착 시간을 결정합니다.

맨 위 항목만 중요합니다. 새로 푸시하는 항목의 도착 시간은 아래 대열보다 항상 늦으므로, 시간은 아래에서 위로 갈수록 늘어납니다. 맨 위 항목보다 늦다는 것은 앞에 있는 모든 차량보다 늦다는 뜻입니다.

순서대로 나열한 예제 1의 차량은 17, 14, 8, 2, 0에 있으며, 거리 나누기 속도는 3/1, 6/3, 12/4, 18/6, 20/2입니다. (3, 1)을 푸시합니다. 14에 있는 차량은 합류합니다. 6 × 1 > 3 × 3은 거짓이기 때문입니다. 8에 있는 차량은 동률입니다. 12 × 1 = 3 × 4이므로 합류하고, 2에 있는 차량도 마찬가지로 합류합니다. 0에 있는 차량은 20 × 1 > 3 × 2이므로 푸시합니다.

알고리즘

자동차 인덱스를 위치를 기준으로 내림차순 정렬합니다.
빈 차량 대열 스택으로 시작합니다.
각 자동차에 대해 dist = target - position[i]를 계산합니다.
스택이 비어 있거나 dist × topSpeed > topDist × speed[i]이면 (dist, speed[i])를 푸시합니다. 그렇지 않으면 해당 자동차는 맨 위 차량 대열에 합류합니다.
스택의 크기를 반환합니다.

def carFleet(target, position, speed):
    # Visit the cars from the one closest to the target backward.
    order = sorted(range(len(position)), key=lambda i: position[i], reverse=True)
    # One entry per fleet: (distance, speed) of the car at its front, which sets its arrival time.
    stack = []
    for i in order:
        dist, spd = target - position[i], speed[i]
        # dist / spd > top_dist / top_spd, compared without division:
        # this car arrives after the fleet ahead, so it never catches it.
        if not stack or dist * stack[-1][1] > stack[-1][0] * spd:
            stack.append((dist, spd))
    return len(stack)

함정과 경계 사례

정확히 같은 경우를 새로운 무리로 세기. 예제 1에서 마일 8과 2 지점의 자동차는 마일 20 지점에서 무리와 만나 합류합니다. 시간이 엄격히 더 늦을 때만 넣으세요.
외적 계산에서의 오버플로. 10^6 × 10^6 = 10^12는 32비트에 들어가지 않습니다. Java, C, C++, C# 및 Rust에서는 곱하기 전에 64비트로 확장하고, R에서는 double을 사용하세요.
잘못된 방향으로 정렬하기. 목적지에서 가장 먼 자동차부터 시작하면 각 자동차를 뒤에 있는 자동차와 비교하게 되며, 뒤에 있는 자동차는 앞의 자동차를 막을 수 없습니다.
position만 정렬하기. 각 속도가 해당 자동차와 함께 유지되도록 인덱스 또는 (position, speed) 쌍을 정렬하세요.

자주 묻는 질문3

Car Fleet의 시간 복잡도는 얼마인가요?

위치 기준 정렬에는 O(n log n)이 걸리고 스택을 사용하는 순회에는 O(n)이 걸리므로, 총 시간 복잡도는 O(n log n)이고 메모리 복잡도는 O(n)입니다. 모든 자동차를 앞에 있는 모든 자동차와 비교하면 O(n²)이 걸립니다.

Car Fleet에서는 왜 스택을 사용할까요?

앞에서부터 차량을 살펴볼 때, 새 차량은 바로 앞에 있는, 즉 마지막으로 형성된 무리와만 비교하면 됩니다. 스택을 사용하면 그 무리를 맨 위에 둘 수 있습니다. 맨 위만 읽으면 되므로 변수 두 개로도 충분합니다. 스택을 사용하면 무리 자체도 유지할 수 있습니다.

부동 소수점 없이 도착 시간을 어떻게 비교하나요?

도착 시간은 dist / speed입니다. 속도는 양수이므로, d1 / s1 > d2 / s2는 d1 × s2 > d2 × s1일 때와 정확히 같습니다. 양변은 최대 10^12의 정수이므로, 64비트 타입으로 계산하면 반올림을 고려할 필요 없이 정확하게 비교할 수 있습니다.

def carFleet(target, position, speed):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자들

target = 20
position = [14, 2, 8, 17, 0]
speed = [3, 6, 4, 1, 2]

예상 출력