[LeetCode] 853. Car Fleet

https://leetcode.com/problems/car-fleet/description/

Algorithm

문제를 제대로 파악하지 못해 헤맸던 문제이다ㅜ. collide 할 경우, 앞에있는 차의 속도를 따라간다. 예를들어 (position,speed)가 (5,2) (7,1) 이 collide 할 경우 2의 speed를 가지는 것이 아니라 1의 speed를 가진다!

본 풀이는 스택을 이용할 수도 있고, 최대 도달시간 변수를 두고 풀 수도있다. 여기선 두가지 풀이를 모두 소개한다.

기본적원리는 모두 같다. 목적지까지 걸리는 시간을 계산하고 이를 앞의 것과 비교해 collide 여부를 판단한다.

 

#1 스택 풀이

1. (position,speed) 리스트를 만든다.
2. 스택을 거리 내림차순으로 정렬한다.
3. for 문을 돌며 각각의 목적지까지 걸리는 시간을 계산해 스택에 넣는다.
   1. 이때, 이전 차보다 목적지까지 걸리는 시간이 더 짧으면 => collide 발생! 이므로 top of stack을 제거한다.

#2 변수이용 풀이

1. (position,speed) 리스트를 만든다.
2. 이 리스트를 거리 내림차순으로 정렬한다.
3. for 문을 돌며 각각의 목적지까지 걸리는 시간(destination_time)을 계산한다.
4. 만약 destination_time이 현재까지의 최대도달시간(cur_time) 보다 오래걸리는 자동차가 나타난다면, fleet을 증가시키고 최대 도달 시간을 업데이트한다.
   1. (같은 의미로, 만약 destination_time이 현재까지의 최대도달시간(cur_time) 보다 적게 걸리는 자동차라면 collide한 것을 의미한다.)

 

---

Python

풀이1

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        pair = [[p, s] for p, s in zip(position, speed)]

        stack = []
        for p, s in sorted(pair)[::-1]: # 거리순 정렬
            stack.append((target - p) / s) # 걸리는 시간 스택에 저장
            # 만약 걸리는 시간 < 이전 Car의 걸리는 시간 이라면 collide !
            if len(stack) >= 2 and stack[-1] <= stack[-2]:
                stack.pop()
        return len(stack)

풀이2

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        pairs = [[p, s] for p, s in zip(position, speed)]

        fleets = curtime = 0

        for dist, speed in sorted(pairs, reverse=True):
            destination_time = (target - dist) / speed
            if curtime < destination_time:
                fleets += 1
                curtime = destination_time
        return fleets

Java

풀이1

class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        if (position.length == 1) return 1;
        Stack<Double> stack = new Stack<>();
        int[][] combine = new int[position.length][2];
        for(int i = 0; i < position.length; i++){
            combine[i][0] = position[i];
            combine[i][1] = speed[i];
        }

        Arrays.sort(combine,java.util.Comparator.comparingInt(o -> o[0]));
        for (int i = combine.length - 1; i >=0; i--){
            double currentTime = (double) (target - combine[i][0]) / combine[i][1];
            if(!stack.isEmpty() && currentTime <= stack.peek()){
                continue;
            } else {
                stack.push(currentTime);
            }
        }
        return stack.size();
    }
}

풀이2

import java.util.Arrays;

class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        int n = position.length;

        int[][] pairs = new int[n][2];
        for(int i = 0; i < n; i++){
            pairs[i][0] = position[i];
            pairs[i][1] = speed[i];
        }

        Arrays.sort(pairs, (a,b)->Integer.compare(b[0],a[0]));

        int fleets = 0;
        double curtime = 0;
        
        for(int i = 0; i < n; i++){
            int dist = pairs[i][0];
            int carSpeed = pairs[i][1];

            double destinationTime = (target - dist) / (double) carSpeed;

            if (curtime < destinationTime) {
                fleets++;
                curtime = destinationTime;
            }
        }
        return fleets;
    }
}