BOJ 1406編集

5809 ワード
2021.01.29 テキストリンク
https://www.acmicpc.net/problem/9471
時間0.3秒、512 MBメモリ
input :
  • 文字列(N 100000を超えない長さ)
  • コマンドの数M(1≦M≦500000)
    • output :
    出力
  • エディタに入力文字列
    • 条件:
  • Lカーソルを左に1マス(文の一番前にカーソルを置く)
    • カーソルを1つ右に移動
  • D(文章の末尾にカーソルを置く)
  • Bカーソル左側の文字を削除(文の先頭にカーソルがある場合は無視)
    削除すると、カーソルが左にスペースを移動しますが、実際にはカーソルの右側の文字は
    • です.
    カーソル左側に文字
  • P$$
    • を追加
  • 段で、命令が実行される前に、カーソルは文の末尾にあるそうです.
    • 最初はcursor変数を直接作成して移動させます.
    Insertメソッドとdelメソッドを使用して実行します.
    ただし,リスト中のメソッドの時間的複雑度は両方ともO(N)であるため,文字列長が10万で命令だけで50万回あると時間制限が短く,当然タイムアウトが発生する.
    これを防止する方法はpopとappendを使用して2つのリストを作成することです.
    dataのカーソルを左に移動すると、dataが表示されます.pop後temp追加します.
    右に移動するとtemppop以降のデータ追加します.
    つまり,アイテムを移動する際には,リストの最後にカーソルが存在すると考えられる.
    また、popの場合、リストの長さは0より大きくなければならないので、条件を追加する必要があります.
    アプリがあれば
    data : abcd
    ->>
    temp : dcba
    もしすべての命令が終わったら.
    リズムを逆さにしなければならない.
    リバース()で反転し、データに加算します.
    import sys

data = list(sys.stdin.readline().strip())
temp = []

for i in range(int(sys.stdin.readline())):
    cmd = sys.stdin.readline().strip()

    if cmd[0] == 'P':
        cmd = cmd.split()
        data.append(cmd[1])

    elif cmd == 'L':
        if len(data) > 0:
            temp.append(data.pop())
            
    elif cmd == 'D':
        if len(temp) > 0:
            data.append(temp.pop())
            
    else:
        if len(data) > 0:
            data.pop()

temp.reverse()
data += temp
print("".join(data))
    💻 グラフィックユーザインタフェース
    Algorithm | SWEA 4408.自分の部屋に戻る(Python)