【LeetCode】853. Car Fleet 解いてみた

はじめに

問題の概要

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

Output: 3

車が到着するまでに何個のグループになっているか。
前の車は抜かせず、グループに集約される。
ターゲットについた時にちょうどグループになってもグループとしてカウント。
単独ゴールもグループとしてカウントされる。

最初に考えた解き方

・追いついたと表現するには？
・それをグループとして管理するには？
・スタックのなかで同じ位置まできたらポップしてしまえばいい。12に到達した数をカウント
forで毎回
・​現在位置にスピードを足す
・​スタックの一個上以上の数になればpopする
​​・その後12以上かチェックしてカウントを更新する

class Solution(object):
    def carFleet(self, target, position, speed):
        """
        :type target: int
        :type position: List[int]
        :type speed: List[int]
        :rtype: int
        """
        stack = []
        count = 0

        # 位置と速度をタプルにしてリストに格納
        for i in range(len(position)):
            stack.append((speed[i], position[i]))

        # 位置の降順にソート
        stack.sort(key=lambda x: x[1])

        while stack:
            # 速度に従って次の位置を計算
            for i in range(len(stack)):
                stackS, stackP = stack[i]
                stack[i] = (stackS, stackP + stackS)

            # **後ろから** ループして追いついた車を削除
            j = 0
            while j < len(stack)-1:
                stackS, stackP = stack[j]
                stackSN, stackPN = stack[j + 1]
                if stackP >= stackPN:
                    stack.pop(j)
                else:
                    j += 1

            # ゴールした車を削除 & カウント
            k = 0
            while k < len(stack):
                stackS, stackP = stack[k]
                if stackP >= target:
                    stack.pop(k)
                    count += 1
                else:
                    k += 1

        return count

何がよくなかったか？

forやwhileを乱用して表現したが、popするときにインデックスがおかしくなってしまったのか正しい答えが得れなかった

解き方

おおむね考え方は似ているがゴール到達までの時間を指標としてつかっている。

つまり、forでターゲットまでループしてたのはだめだ！

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        pair = [(p, s) for p, s in zip(position, speed)]
        pair.sort(reverse=True)
        stack = []
        for p, s in pair:  # Reverse Sorted Order
            stack.append(float(target - p) / s)
            if len(stack) >= 2 and stack[-1] <= stack[-2]:
                stack.pop()
        return len(stack)

ループせずに簡単に評価できる指標をつくるのが大事なんだ

ループさせて、、、と考えてしまう癖があるようだ
ではなくどう全ての要素を一つの指標で比較出来るかを考えなければ

参考資料

おわりに・まとめ

複雑になってしまっているなと自覚したら今一度簡単になる方法を見つめ直そう！