[LeetCode 해석 및 풀이] 853. Car Fleet

LeetCode 문제 해석 및 풀이 방법

 

문제 853. Car Fleet(자동차 함대)

바로가기

 

문제 설명

영문

There are n cars going to the same destination along a one-lane road. The destination is target miles away.

You are given two integer array position and speed, both of length n, where position[i] is the position of the ith car and speed[i] is the speed of the ith car (in miles per hour).

A car can never pass another car ahead of it, but it can catch up to it and drive bumper to bumper at the same speed. The faster car will slow down to match the slower car's speed. The distance between these two cars is ignored (i.e., they are assumed to have the same position).

A car fleet is some non-empty set of cars driving at the same position and same speed. Note that a single car is also a car fleet.

If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.

Return the number of car fleets that will arrive at the destination.

 

한글

n대의 자동차가 같은 목적지로 한 도로에서 가고 있습니다. 목적지는 target 마일 밖에 있습니다.

 

길이 n의 두 개의 정수 배열 position, speed가 주어집니다. position[i]은 i번째 차의 위치이고, speed[i]는 i번째 차의 속도입니다.(miles/h)

 

한 차는 절대로 다른 차를 지나쳐서 가지 않지만, 따라잡을 수는 있고 범퍼를 맞대고 같은 속도로 운전하게 됩니다. 더 빠른 차는 느린 차의 속도에 맞게 느려집니다. 두 차 사이의 거리는 무시 가능합니다. (즉, 같은 위치에 있다고 가정합니다.)

 

"자동차 함대"란 같은 위치와 같은 속도를 가진 차들의 집단을 뜻합니다. 자동차 한 대도 자동차 함대임을 유의하세요.

 

자동차가 목적지 지점에서 바로 자동차 함대를 따라잡는 경우에도 여전히 하나의 자동차 함대로 간주됩니다.

 

목적지에 도착했을 때의 자동차 함대의 수를 구해주세요.

 

제한조건

• n == position.length == speed.length
• 1 <= n <= 10^5
• 0 < target <= 10^6
• 0 <= position[i] < target
• All the values of position are unique.
• 0 < speed[i] <= 10^6

 

입출력 예

입력	출력
target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]	3
target = 10, position = [3], speed = [3]	1
target = 100, position = [0,2,4], speed = [4,2,1]	1

 

 

해답 및 해설

파이썬 (Python)

뒤쪽(position이 작은) 차부터 따지기

neetcode 로드맵에서 stack을 이용해 풀라고 나와있었다는 점, 차가 따라잡히지 않으면 함대가 계속 추가되지만, 따라잡히면 차가 사라진다는 점, 그리고 이전 문제인 일일 기온 문제에 영감을 받아 문제를 풀었다.

 

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        cars_info = sorted(zip(position,speed), key=lambda x: x[0])
        stack = []

        for cur_pos, cur_spd in cars_info:
            while 1:
                if not stack:
                    stack.append((cur_pos, cur_spd))
                    break

                last_pos, last_spd = stack[-1]

                if cur_spd >= last_spd:
                    stack.append((cur_pos, cur_spd))
                    break
                
                crash_point = (cur_pos*last_spd - last_pos*cur_spd) / (last_spd - cur_spd)

                if crash_point > target:
                    stack.append((cur_pos, cur_spd))
                    break
                
                stack.pop()
        
        return len(stack)

우선 차들의 정보를 (위치, 속도)형태의 튜블로 묶은 후, 위치에 따라 정렬해준다. 그 후 앞에 있는 차가 뒤에 있는 차보다 빠를 때는 stack에 추가해준다. stack에 아무 차도 없을 때도 추가해준다.

 

앞에 있는 차가 뒤에 있는 차보다 느릴 때는 충돌지점을 계산하는데, 그 값은 (x2*v1 - x1*v2)/(v1-v2)을 계산하면 나오게 된다. (식 정리 과정은 생략) 만약 충돌지점이 target보다 뒤쪽이면 하나의 함대로 합쳐지지 않으므로 stack에 추가해준다. 만약 충돌 지점이 target 앞쪽이라면 stack에 충돌하지 않는 차들이 남을 때까지 계속 빼내어준다. 그러면 stack에는 함대의 맨 앞에 있는 차들의 정보만 남게 된다.

 

마지막에 stack에 남아있는 차 정보의 갯수가 함대의 갯수이므로 해당 값을 반환해준다.

 

 일일 기온 문제에서 했던 것처럼 문제를 한번 푼 후 코드를 정리?해주었다.

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        car_row = sorted(range(len(position)), key=lambda i: position[i])
        s = []
        t = target

        for i in car_row:
            x_c, v_c = position[i], speed[i]
            if s: x_l, v_l = position[s[-1]], speed[s[-1]]

            while s and v_c < v_l and (t-x_c)*v_l>=(t-x_l)*v_c:
                s.pop()
                if s: x_l, v_l = position[s[-1]], speed[s[-1]]
            s.append(i)

        return len(s)

 우선 stack에는 index만 넣도록 바꾸었고, 숫자 계산시에 나누기가 들어가는게 거슬려 그냥 현재 차랑 이전 차가 target에 도착하는 시간이 어떤지만 비교하고 그 식을 정리해주었다. 현재 차가 도착 시간이 더 느리다면 뒷 차들이 target에 도착하기 전에 충돌한다는 이야기므로 stack에서 차들을 빼주는 방식으로 했다.

 

앞쪽(position이 큰) 차부터 따지기

다른 사람들의 풀이 방식을 보니 이런 풀이가 있었다.

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        car_row = sorted(range(len(position)), key=lambda i: position[i], reverse=True)
        s = 1
        t = target
	
        x_l, v_l = position[car_row[0]], speed[car_row[0]]
        for i in car_row[1:]:
            x_c, v_c = position[i], speed[i]

            if v_c < v_l or (t-x_c)*v_l>(t-x_l)*v_c:
                s += 1
                x_l, v_l = x_c, v_c

        return s

 나는 지금까지 정렬 방식을 맨 뒤에 있는 차부터 맨 앞에 있는 차 순으로 했었는데, 반대로 생각해 맨 앞에 있는 차부터 따지는 방식이 있었다. 그 후 뒷 차가 도착시간이 더 빠르면 현재 기존 앞차의 함대에 추가되므로 함대 갯수를 증가시키지 않고, 도착시간이 느리면 함대 갯수를 증가하며 푸는 방식이었다. (내가 본 풀이에서는 도착시간을 미리 계산해주어 비교해줬지만, 내가 새로 짠 코드에선 그러진 않았다. 나누기 연산은 싫어서...)

이 풀이는 스택으로 넣고 빼는 작업이 없어서 그런지 더 빨랐다. 아마 도착시간을 미리 계산해서 저장해두었으면 더 빨랐을듯 싶다.

 

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        stack = zip(position, speed)
        stack = sorted(stack, key=lambda x: x[0])

        cur_node = stack.pop()
        cur_fleet_time = (target - cur_node[0])/cur_node[1]
        result = 1

        while stack:
            cur_node = stack.pop()
            cur_time = (target - cur_node[0])/cur_node[1]
            if cur_time > cur_fleet_time:
                result += 1
                cur_fleet_time = cur_time
        
        return result

참고한 풀이