[Python]伯準5397キーロック(Deque)

📌 質問する

昌英は江山のパスワードを盗むため、江山が使っているパソコンに鍵を取り付けた.数日の待ち時間を経て、昌英はついに江山がパスワードウィンドウに入力した字を手に入れた.
キーを押すと、ユーザーがキーボードを押したすべてのコマンドが記録されます.したがって、江山がパスワードを入力すると、矢印やbackspaceを入力しても正しいパスワードが検出される.
江山がパスワードウィンドウに入力した鍵が与えられた場合、江山のパスワードを識別するプログラムを作成してください.江山がキーボードで入力したキーは、大文字、小文字、数字、スペース、矢印です.

入力

最初の行は、テスト例の数を示します.各テスト例は1行で構成され、江山入力の順序に従って長さLの文字列が与えられる.(1≦L≦100000)江山がbackspaceを入力した場合は「-」を与える.このとき、カーソルの直前に文字がある場合は消去します.矢印は「<」と「>」と入力されます.このとき、カーソルの位置が移動可能であれば、1を左または右に移動します.残りの文字はパスワードの一部です.もちろん、後でbackspaceで削除できます.カーソルの位置が最後の行でない場合は、カーソルとカーソルの右側のすべての文字が1つ右に移動します.

しゅつりょく

各テストボックスに対して、江山のパスワードを出力します.パスワードの長さは常にゼロより大きい.

入力例1

2
<<BP<A>>Cd-
ThIsIsS3Cr3t

サンプル出力1

BAPC
ThIsIsS3Cr3t

📌 に答える

💬 Code

import sys
from collections import deque
input = sys.stdin.readline

for _ in range(int(input())):
    pw = input().rstrip()
    left, right = [], deque()

    for now in pw:
        if now == '<' and left:
            right.appendleft(left.pop())
        elif now == '>' and right:
            left.append(right.popleft())
        elif now == '-' and left:
            left.pop()
        elif now.isalnum():
            left.append(now)

    print(''.join(map(str, left+list(right))))

💡 Solution

커서を中央に配置し、カーソル左側文字を含むleftとカーソル右側文字を含むrightをそれぞれ管理する.
タイムアウトを避けるために、カーソルを移動せずに1ラウンドで1文字移動します.⑤のように1番目の位置を追加する必要がある場合と、
そうする前に、、、、、と初めて提出されたコードはこうです.カーソルをインデックスとして1つずつ移動し、文字の挿入/削除を行い、挿入/削除時に後ろのすべての文字の位置を移動する必要があるため、タイムアウトします.

import sys
from collections import deque
input = sys.stdin.readline

for _ in range(int(input())):
    pw = list(input().rstrip())
    q = deque(pw)

    idx = 0
    result = []
    while q:
        now = q.popleft()
        if now == '<' and idx > 0:
            idx -= 1
        elif now == '>' and idx <= len(result)-1:
            idx += 1
        elif now == '-' and idx > 0:
            idx -= 1
            del result[idx]
        elif now.isalnum():
            result.insert(idx, now)
            idx += 1

    print(''.join(map(str, result)))