[1406]編集|白駿銀色2

🔎 問題の説明

質問リンク
エディタには、文の一番前(最初の文字の左側)、文の一番後ろ(最後の文字の右側)、または文の真ん中の任意の位置(連続する2文字の間)にカーソルを置く「カーソル」というものがあります.つまり、現在のエディタに長さLの文字列を入力すると、カーソルはL+1の位置に配置できます.
このエディタでは、次のコマンドがサポートされています.

L:カーソルを左に1マス移動(文の一番前にカーソルを置く)

D:カーソルを右に1マス移動(文章の末尾にカーソルを置く)

B:カーソルの左側の文字を削除します(カーソルが文の先頭にある場合は無視します).
削除すると、カーソルは1つ左に移動しますが、実際のカーソル位置は

です.

P $ : $カーソルの左側に名前の文字

を追加
すべてのコマンドを実行したら、エディタに入力した文字列を取得するプログラムを作成します.しかし、コマンドが実行される前に、カーソルは文の末尾にあると言われています.

入力

最初の行には、初期入力エディタの文字列が表示されます.この文字列の長さはNです.
2行目には、入力するコマンドの数を示す整数Mが与えられる.
3行目から、M行の間に入力するコマンドを順番に与えます.

しゅつりょく

最初の行ですべてのコマンドを実行した後、出力エディタに入力した文字列.
せいげんじょうけん

0 ≤ N ≤ 100,000

文字列は、英語の小文字のみで構成されています.

1 ≤ M ≤ 500,000

命令は、上述した4つの形式の1つのみで与えられる.

🧪 JAvaコード

public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        LinkedList<Character> sL = new LinkedList<>();
        LinkedList<Character> sR = new LinkedList<>();
        //str.length <= 100,000
        String str = br.readLine(); //스트링 입력
        for(char c : str.toCharArray()){
            sL.add(c);
        }
        //(1 ≤ M ≤ 500,000) 명령어수
        int M = Integer.parseInt(br.readLine());
        while(0 < M--){//sL.size()가 사실 상 커서위치이다.
            char [] cmd = br.readLine().toCharArray();
            if(cmd[0] == 'L' && !sL.isEmpty()) sR.push(sL.removeLast());    //왼쪽마지막->오른쪽첫번째로 이동
            if(cmd[0] == 'D' && !sR.isEmpty()) sL.add(sR.pop());    //오른쪽첫번째->왼쪽마지막으로 이동
            if(cmd[0] == 'B' && !sL.isEmpty()) sL.removeLast(); //왼쪽마지막 제거.
            if(cmd[0] == 'P') sL.add(cmd[2]);   //왼쪽마지막에 밀어넣기
        }
        while(!sL.isEmpty() || !sR.isEmpty()){//sL부터 출력 후 sR 출력
            bw.write( !sL.isEmpty() ? sL.pop() : sR.pop());
        }
        bw.flush();
        bw.close();
}

最初は1つの集合しか書いていませんでしたがタイムアウトしたので2つで解きました

🧊 Pythonコード

import sys
import collections as c
stack = c.deque(input()) #문자열 deque로 
input() #명령어 수 
C = len(stack) #커서위치
for cmd in sys.stdin:
    if cmd[0] == 'P':
        stack.append(cmd[2])
        C += 1
    if C and 'L' == cmd[0]:
        stack.rotate(1)
        C -= 1
    if C and 'B' == cmd[0]:
        stack.pop()
        C -= 1
    if cmd[0] == 'D' and C < len(stack):
        stack.rotate(-1)
        C += 1
stack.rotate(C)
print(''.join(stack)) #문자열로 변환

Pythonはdequeを使用して時間の複雑さを減らすことができます.
rotate()を使用して、カーソルを常に最後に向けます.そして、コマンド終了時にカーソル位置を中心に回転します.

💡 rotate()

rotate()の方法は、Collectionのクラスのdequeとともに使用することができる.
Pythonがdequeを使うのはリストより速いからです.
Listの時間複雑度はO(n)O(n)O(n)であり,dequeはO(1)O(1)O(1)であった.
したがってdequeは、append/remove/push/pop演算を大量に実行するアルゴリズムで機能する可能性がある.
dequeにはrotate()という方法があります.rotateにはループ機能があります.

サンプルコード

from collections import deque
stack = deque([1, 2, 3, 4, 5])

stack.rotate(1) #[5, 1, 2, 3, 4]
stack.rotate(1) #[4, 5, 1, 2, 3]
stack.rotate(-1) #[5, 1, 2, 3, 4]
stack.rotate(-3) #[3, 4, 5, 1, 2]