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

<!--

## 技術記事のタイトル

【LeetCode】853. Car Fleet 解いてみた
最も伝えたいこと。
簡潔かつ分かりやすく過不足ないタイトルを考えましょう。

### 【 】(墨付き括弧)

- 【言語やサービス】
    - 例1.【Python】すぐにpytestで単体テストを実行するまでの手順
- 【言いたいこと】
    - 例1.【必見】Objectはどこに消えた？
- 【前提】
    - 例1.【個人開発】○○を○○できるサービスをリリースしました
    - 例2.【初心者向け】Reactとはそもそも何なのか説明します
- 【続き物の番号】
    - 例1.【2024年版】新入社員向け研修資料を公開します
    - 例2.【環境構築編】Windows11でPythonを実行するまで

【前提】詳しいタイトル【言語やサービス】のように、複数を併用するパターンもあります。

-->

## はじめに
<!--
何についての記事なのか、誰に向けた記事なのかを簡単に説明しましょう。
-->

### 問題の概要
<!--
読んだら何がわかるようになるのか、何ができるようになるのかを書きましょう。
-->

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するときにインデックスがおかしくなってしまったのか正しい答えが得れなかった


## 解き方
<!--
章全体の要約や、何について書くのかをここに書きます。
記事が長い時や資料として作るときは番号を振ることをおすすめします。
章を増やすときは章から項までをコピーしてください。
-->




### おおむね考え方は似ているがゴール到達までの時間を指標としてつかっている。
<!--
記事の主要な部分です。ここに思い思いの内容を書いていってください。

画像やGIFがあると分かりやすいです。
画像があるとUIが変わったとしても読者がアタリをつけて対応しやすくなります。

コードを記載する場合は必ずコードブロックを使いましょう。
バッククオート3つで囲んでください。
```python:表示名

    print('Hello World')
    
```
-->
つまり、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)
```



#### ループせずに簡単に評価できる指標をつくるのが大事なんだ
<!--
より詳細な内容を書いたり、事例を挙げたりするときに使います。
- 節の内容の列挙
- 節の補足事項
- 例外
-->
ループさせて、、、と考えてしまう癖があるようだ
ではなくどう全ての要素を一つの指標で比較出来るかを考えなければ


## 参考資料
<!--

https://qiita.com

[リンク1](https://qiita.com)
-->

https://leetcode.com/problems/car-fleet/
## おわりに・まとめ
<!--
どちらかを書きます。あってもなくても良いです。
-->

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