[1406]編集

🔗 質問リンク

https://www.acmicpc.net/problem/1406

問題の説明

線を1本実現する簡単なエディタ.このエディタには英語の小文字しか記録できません.最大600,000文字を入力できます.
このエディタには、文の一番前(最初の文字の左側)、文の一番後ろ(最後の文字の右側)、または文の真ん中の任意の位置(連続する2文字の間)にカーソルを置く「カーソル」というものがあります.つまり、現在のエディタに長さLの文字列を入力すると、カーソルはL+1の位置に配置できます.
このエディタでは、次のコマンドがサポートされています.

L	커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)
D	커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)
B	커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨)
	삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임
P $	$라는 문자를 커서 왼쪽에 추가함

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

⚠▼制限

最初の行には、初期入力エディタの文字列が表示されます.

この文字列の長さはNで、英語の小文字のみで、長さは100000を超えない.

2行目には、入力する命令数を示す整数M(1≦M≦500000)が与えられる.

3行目から、M行の間に入力するコマンドを順番に与えます.

コマンドは、上記の4つのいずれかの形式でのみ与えられます.

💡 プール(言語:Java)

最初に解いた接着剤はタイムアウトと判定された.StringBuilderで位置を記録するidx変数を使用してターゲット位置で削除、挿入などの操作を行う仕組み.for文中のO(n)O(n)O(n)O(n)O(n)O(n)O(n)O(n)n)および奥のif文ではStringBuilderのdelete法とinsert法が他の文字列を削除して挿入して並べ替えるため,再び淘汰され,O(n)O(n)O(n^2)O(n 2)O(n 2)の時間的複雑さが必要となるためである.
他人の解答を見た後,スイッチドア内でスタックを用いてO(1)O(1)O(1)O(1))を行う時間的複雑さのアルゴリズムを参考にした.左側には既存の文字列を挿入し、カーソルの移動に応じて右側のスタックに値を配置および減算できる構造があります.最後に、左側のスタックの値を右側のスタックに入れ、順番にポップアップして出力します.しかしこれもタイムアウトと判定される.ㅡㅡ; BufferedWriterで出力時間を減らせば通過と判定される.
しょかい

public class Main {
    private static StringBuilder strBuilder;
    private static int idx;

    private static void editor(String command) {
            if (command.equals("L")) {
                if (idx != 0) {
                    idx--;
                }
            } else if (command.equals("D")) {
                if (idx != strBuilder.length()) {
                    idx++;
                }
            } else if (command.equals("B")) {
                if (idx != 0) {
                    strBuilder.deleteCharAt(idx-1);
                    idx--;
                }
            } else {
                strBuilder.insert(idx, command.charAt(2));
                idx++;
            }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        int n = Integer.parseInt(br.readLine());
        strBuilder = new StringBuilder(str);
        idx = strBuilder.length();
        for (int i = 0; i < n; i++) {
            editor(br.readLine());
        }
        System.out.println(strBuilder);
    }
}

改草

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String str = br.readLine();
        int n = Integer.parseInt(br.readLine());
        // 입력받은 문자열은 left스택에 넣어주고, 명령에 따라 right스택과 서로 주고 받는다.
        Stack<String> rightStack = new Stack<>();
        Stack<String> leftStack = new Stack<>();
        for (String chr : str.split("")) {
            leftStack.push(chr);
        }
        for (int i = 0; i < n; i++) {
            String command = br.readLine();
            switch (command) {
                case "L" :
                    if (!leftStack.isEmpty()) {
                        rightStack.push(leftStack.pop());
                    }
                    break;
                case "D" :
                    if (!rightStack.isEmpty()) {
                        leftStack.push(rightStack.pop());
                    }
                    break;
                case "B" :
                    if (!leftStack.isEmpty()) {
                        leftStack.pop();
                    }
                    break;
                default :
                    leftStack.push(String.valueOf(command.charAt(2)));
            }
        }
        // 출력값은 left 스택의 맨 아래 원소부터이다. 그리고 right 스택의 원소와 합쳐야 하므로
        // left 스택값들을 right 스택으로 옮겨주면 원래 출력할 문자열 순서가 된다.
        while (!leftStack.isEmpty()) {
            rightStack.push(leftStack.pop());
        }
        // right 스택 문자열을 위에서 부터 pop한다. 출력을 빠르게하기 위해 BufferedWriter 사용
        while (!rightStack.isEmpty()) {
            bw.write(rightStack.pop());
        }
        // 모두 출력하고 버퍼를 비움
        bw.flush();
        bw.close();
    }
}