[LeetCode][Kotlin] 853. Car Fleet

853. Car Fleet

There are n cars at given miles away from the starting mile 0, traveling to reach the mile target.

 

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

 

A car cannot pass another car, but it can catch up and then travel next to it at the speed of the slower car.

 

A car fleet is a car or cars driving next to each other. The speed of the car fleet is the minimum speed of any car in the fleet.

 

If a car catches up to a car fleet at the mile target, it will still be considered as part of the car fleet.

 

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

출발 마일 0에서 주어진 마일 떨어진 곳에 n대의 차량이 있으며, 마일 목표에 도달하기 위해 이동하고 있습니다. 

두 개의 정수 배열 position과 speed가 주어지며, 둘 다 길이가 n입니다. 여기서 position[i]는 i번째 차량의 출발 마일이고 speed[i]는 i번째 차량의 시속 마일 속도입니다. 

차량은 다른 차량을 추월할 수 없지만, 따라잡은 다음 더 느린 차량의 속도로 그 옆을 지나갈 수 있습니다. 

차량 함대는 서로 옆을 지나가는 차량 또는 차량들입니다. 차량 함대의 속도는 함대에 있는 모든 차량의 최소 속도입니다. 

차량이 마일 target에서 차량 함대를 따라잡으면 여전히 차량 함대의 일부로 간주됩니다. 

목적지에 도착할 차량 함대의 수를 반환합니다.

 

Example 1:

Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]

Output: 3

Explanation:

• The cars starting at 10 (speed 2) and 8 (speed 4) become a fleet, meeting each other at 12. The fleet forms at target.
• The car starting at 0 (speed 1) does not catch up to any other car, so it is a fleet by itself.
• The cars starting at 5 (speed 1) and 3 (speed 3) become a fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.

 

Example 2:

Input: target = 10, position = [3], speed = [3]

Output: 1

Explanation:

There is only one car, hence there is only one fleet.

 

Example 3:

Input: target = 100, position = [0,2,4], speed = [4,2,1]

Output: 1

Explanation:

• The cars starting at 0 (speed 4) and 2 (speed 2) become a fleet, meeting each other at 4. The car starting at 4 (speed 1) travels to 5.
• Then, the fleet at 4 (speed 2) and the car at position 5 (speed 1) become one fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.

 

Constraints:

• 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

---

코드 1

class Solution {
    fun carFleet(target: Int, position: IntArray, speed: IntArray): Int {
        val pair = position.zip(speed).sortedByDescending { it.first }
        val stack = mutableListOf<Double>()

        for ((p, s) in pair) {
            val time = (target - p).toDouble() / s
            stack.add(time)
            if (stack.size >= 2 && stack[stack.size - 1] <= stack[stack.size - 2]) {
                stack.removeLast()
            }
        }
        
        return stack.size
    }
}

 

코드 2

class Solution {
    fun carFleet(target: Int, position: IntArray, speed: IntArray): Int {
        val pair = position.zip(speed).sortedByDescending { it.first }
        
        var fleets = 1
        var prevTime = (target - pair[0].first).toDouble() / pair[0].second
        for (i in 1 until pair.size) {
            val (p, s) = pair[i]
            val currTime = (target - p).toDouble() / s
            if (currTime > prevTime) {
                fleets++
                prevTime = currTime
            }
        }
        
        return fleets
    }
}