[Java] BOJ 1406 에디터

1406번: 에디터

---

오답 코드

- 삽입/삭제가 자주 일어나는 문제라 ArrayList가 아니라 LinkedList를 선택함

- 하지만 가장 마지막에 add하는 경우에서 100,000(최초 입력 길이) * 500,000(명령어 수)로 인해 시간 초과 발생

import java.io.*;
import java.util.*;

public class Main {

    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static String str;
    static int N, pos;
    static LinkedList<Character> list;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        str = br.readLine();
        N = Integer.parseInt(br.readLine());

        list = new LinkedList<>();
        for (int i = 0; i < str.length(); i++) {
            list.add(str.charAt(i));
        }

        pos = str.length();
        for (int i = 0; i < N; i++) {
            str = br.readLine();

            char c = str.charAt(0);
            if (c == 'L') {
                if (pos > 0) {
                    pos--;
                }
            } else if (c == 'D') {
                if (pos < list.size()) {
                    pos++;
                }
            } else if (c == 'B') {
                if (pos > 0) {
                    list.remove(--pos);
                }
            } else {
                char alph = str.charAt(2);
                list.add(pos++, alph);
            }
        }

        for (char c : list) {
            bw.write(c);
        }
        bw.flush();
    }

}

---

정답 코드

- 커서 위치에 따라 2개의 스택을 활용하여 구현

- 커서 왼쪽 stack1 / 커서 오른쪽 stack에 저장

- 마지막엔 stack1을 stack2에 옮겼다가 출력

import java.io.*;
import java.util.*;

public class Main {

    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static String str;
    static int N, pos;
    static Stack<Character> stack1, stack2;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        str = br.readLine();
        N = Integer.parseInt(br.readLine());

        stack1 = new Stack<>();
        stack2 = new Stack<>();

        for (int i = 0; i < str.length(); i++) {
            stack1.push(str.charAt(i));
        }

        pos = str.length();
        for (int i = 0; i < N; i++) {
            str = br.readLine();

            char c = str.charAt(0);
            if (c == 'L') {
                if (!stack1.isEmpty()) {
                    stack2.push(stack1.pop());
                }
            } else if (c == 'D') {
                if (!stack2.isEmpty()) {
                    stack1.push(stack2.pop());
                }
            } else if (c == 'B') {
                if (!stack1.isEmpty()) {
                    stack1.pop();
                }
            } else {
                char alph = str.charAt(2);
                stack1.push(alph);
            }
        }
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }

        while (!stack2.isEmpty()) {
            bw.write(stack2.pop());
        }

        bw.flush();
    }
}