Pythonで停止したときに動く動物の最終的な位置を取得するプログラム

一部の動物の初期状態を表す文字列sがあるとします。各動物は、次の3つの値のいずれかを取ることができます。Lは、動物が左に移動したことを示します。 Rは、動物が右に移動したことを示します。 @は、動物が静止していることを示します。ある方向に移動する動物は、反対方向から力を受けない限り、他の動物を拾います。その後、静止します。動物が動きを止めたときの各動物の向きを見つける必要があります。

したがって、入力がs ="@@ L @ R @@@@ L"の場合、出力は "LLL @ RRRLLL"

これを解決するには、次の手順に従います-

• レベル：=sと同じサイズのリストで、-1で埋めます

• q：=両端キュー

• idxが0からsのサイズの範囲にある場合は、実行してください

  • s [idx]が「R」と同じであるか、s [idx]が「L」と同じである場合、

    • qの最後に（idx、0、s [idx]）を挿入します

• l：=sの文字の新しいリスト

• qが空でない間、実行します

  • （idx、new_level、dir）：=qの要素を残し、qから削除します

  • レベル[idx]が-1と同じ場合、

    • レベル[idx]：=new_level

    • l [idx]：=dir

    • dirが「R」と同じでidx+1

      • qの最後に（idx + 1、new_level + 1、dir）を挿入します

    • それ以外の場合、dirが「L」と同じでidx-1> =0の場合、

      • qの最後に（idx-1、new_level + 1、dir）を挿入します

  • それ以外の場合、levels [idx]がnew_levelと同じである場合、

    • l [idx]がdirと同じでない場合、

      • l [idx]：="@"

• l

  の要素を結合して文字列を返します

例

理解を深めるために、次の実装を見てみましょう-

from collections import deque
class Solution:
   def solve(self, s):
      levels = [-1 for i in s]
      q = deque()
      for idx in range(len(s)):
         if s[idx] == "R" or s[idx] == "L":
            q.append((idx, 0, s[idx]))
      l = list(s)
      while q:
         idx, new_level, dir = q.popleft()
         if levels[idx] == -1:
            levels[idx] = new_level
            l[idx] = dir
            if dir == "R" and idx + 1 < len(l):
               q.append((idx + 1, new_level + 1, dir))
            elif dir == "L" and idx - 1 >= 0:
               q.append((idx - 1, new_level + 1, dir))
         elif levels[idx] == new_level:
            if l[idx] != dir:
               l[idx] = "@"
      return "".join(l)
ob = Solution()
s = "@@L@R@@@@L"
print(ob.solve(s))

入力

"@@L@R@@@@L"

出力

LLL@RRRLLL