문제 링크: https://www.acmicpc.net/problem/1406

ArrayList를 만들자

ArrayList를 생성하고 반복문으로 명령어 조건에 맞게 실행했다.시간초과 나왔다.
즉 index 변수는 커서의 위치를 담당하고, 명령어(L/D/B/P)에 따라 LinkedList 커서의 위치(인덱스)를 찾아 삽입/삭제하는 것이다.
=> 커서는 이동하지 않고 삽입/삭제를 해보자!

Stack을 사용하자

스택은 그림처럼 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어있다.

스택의 시간 복잡도는 다음과 같다.

• push: O(1)
• pop: O(1)
• search: O(n)

이 예시는 위치를 나타내기 위해 자료를 움직이므로 O(1)의 시간 복잡도를 갖는다.

예제 1에서

abcd
3
P x
L 
P y

커서는 항상 입력 문자열의 맨 뒤에 위치한다. -> 문자열을 모두 왼쪽 스택에 넣는다.
커서가 아래로 이동하면, 왼쪽 스택의 상단 요소를 오른쪽 스택에 pop() 한다. 오른쪽 스택의 가장 상단 요소를 왼쪽 스택에 pop()하면서 커서가 이동하는 것처럼 보이게 한다.

모든 명령어가 처리되면 스택의 LIFO 구조에 맞게 왼쪽 스택의 모든 요소를 오른쪽 스택에 옮기고 오른쪽 스택을 pop() 하여 출력한다.

public class P1406 {

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/Algorithm/P1406/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        Stack<Character> leftStack = new Stack<>();
        Stack<Character> rightStack = new Stack<>();

        String str = br.readLine();
        for (int i = 0; i < str.length(); i++) {
            leftStack.push(str.charAt(i));
        }

        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            String command = br.readLine();

            switch (command.charAt(0)) {
                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;
                case 'P':
                    leftStack.push(command.charAt(2));
                    break;
                default:
                    break;
            }
        }

		// 출력을 위해 leftStack에서 rightStack으로 이동시킨다.
        while (!leftStack.isEmpty()) {
            rightStack.push(leftStack.pop());
        }
        
        // rightStack에서 하나씩 pop하면서 출력한다.
        while (!rightStack.isEmpty()) {
            bw.write(rightStack.pop());
        }
        bw.flush();
        bw.close();
    }
}

Ref

• https://minhamina.tistory.com/17