[BOJ 백준] - 에디터 1406 Java

4개 명령어를 가진 텍스트 에디터를 구현해야 하는 문제이다.

중간에 삽입, 삭제 등 연산이 빈번히 발생하기 때문에 가장 먼저 LinkedList를 생각하고 구현했다.

어떤 방법으로도 LinkedList로는 시간초과를 벗어나지 못했다..

삽입, 삭제에는 효율적인 자료구조이지만 cursor까지 데이터를 스캔할 때 O(N)의 성능을 보이는 것이 문제인 것 같다.

시간초과를 해결하기 위해 삽입,삭제,조회 모두 O(1)의 성능을 갖는 Stack 자료구조를 사용했다.

두 개 Stack을 사용한다.

• leftStack
• rightStack

뽀인트
leftStack의 top을 cursor의 위치와 동일하게 만들어준다.

각 명령어에 대한 동작을 살펴보자.

P : 삽입
cursor의 위치와 leftStack의 top이 동일해야 하기 때문에 P에 의해 텍스트가 삽입될 때는 leftStack에 push 한다.

B : 삭제
leftStack의 top에 값이 있다면 pop한다.
자연스럽게 커서의 위치에서 데이터를 지우게 된다.

L : 왼쪽으로 cursor 이동
cursor와 leftStack의 top의 위치는 동일해야 한다.
cursor가 왼쪽으로 이동하므로 leftStack의 top의 위치도 감소시켜줘야 한다.
이 때 leftStack에서 빠지는 값은 rightStack으로 넣어준다.

D 오른쪽으로 cursor 이동
rightStack에서 leftStack으로 pop 후 push한다.

모든 명령어를 수행하고 출력할 때에는 스택의 특성상 뒤집어진 문자들을 다시 원복시켜줘야 한다.

남아있는 leftStack의 모든 값을 rightStack으로 옮기고 다시 leftStack으로 옮기면 자연스럽게 원래 상태로 뒤집어진다.

코드

public class Q1406_2 {

    public static void main(String[] args) throws IOException {
        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 initialStr = br.readLine();
        int m = Integer.parseInt(br.readLine());

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

        for (int i=0;i<m;i++) {
            String commandLine = br.readLine();
            char command = commandLine.charAt(0);

            switch (command) {
                case 'P':
                    leftStack.push(commandLine.charAt(2));
                    break;
                case 'B':
                    if (!leftStack.isEmpty()) leftStack.pop();
                    break;
                case 'L':
                    if(!leftStack.isEmpty()) rightStack.push(leftStack.pop());
                    break;
                case 'D':
                    if (!rightStack.empty()) leftStack.push(rightStack.pop());
                    break;
                default: break;
            }
        }
        while(!leftStack.empty()) {
            rightStack.push(leftStack.pop());
        }
        while (!rightStack.empty()) {
            bw.write(rightStack.pop());
        }
        bw.close();
        br.close();
    }
}