始めに
今回はLeetCodeのMedium問題に挑戦してみた
結論から言うと自力で解くことができなかったので素晴らしい解答をしてる方のコードを参考にしました。
間違いやより良い解法があればご指摘お願いします🙇♂
問題
片側1車線の道路にn台の車が走っており、前の車に追いついたらその車で同じ速度で走る。
同じ速度で走る車は1グループとみなし、最終的に目的地に到着するグループ数を計算する問題。
ちなみに目的地まで追いつかなかったら1台を1つのグループとしてカウントする
正直問題文も長いし、色々理解するのに時間がかかった...
考察
この問題は目的地までに前の車に追いつくか？と言う視点が重要
目的地までの距離をスタックで管理すれば解けそうだ
- 位置と速度のペアが作り、ソートすれば計算しやすいかも
- 追い越しは禁止(追いついたら同じ速度になり車団の一部になる)
- 目的地までの距離の計算方法
- 目的地までの距離をスタックで管理
前の車に追いついたら速度は前の車と同じになるので後ろの車はスタックから消す。
これを繰り返すことでstackの数 = 車のグループ数
解法
位置と速度をグループ化
zipを使わずにfor文を回して[[position, speed]]の形にしても良い。
そして、グループ化したpairを降順にソートして目的地までの距離が近い順に並べる
def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
# [(position, speed)]のデータ構造にする
# zipでまとめると楽
pair = [(p, s) for p, s in zip(position, speed)]
pair.sort(reverse=True)
目的地までの時間をスタックに追加
目的地までの時間 = (target - p) / s
stack = []
for p, s in pair:
stack.append((target - p) / s)
1台前の車に追いついた場合、後方の車を削除
考察で書いた通りお越しは禁止なので追いついた時点で前の車の速度と同じになる。
つまり、1つのグループとなるので後方の車はスタックから削除する
if len(stack) >= 2 and stack[-1] <= stack[-2]:
stack.pop()
スタックの数を返す
スタックの数 = 車のグループ数となる
return len(stack)
コードの全体を載せておく
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:
stack.append((target - p) / s)
if len(stack) >= 2 and stack[-1] <= stack[-2]:
stack.pop()
return len(stack)
感想
正直この辺の問題は初見で解けないことが増えてきた...
特にEasyまではアルゴリズムを知っているだけで解ける問題があったが、Medium以上はアルゴリズム+考察力が必要。
定期的に復習しながらいろんなパターンを経験するしかないかな