[BOJ] 1406번 에디터 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

    static int M;
    static String input;
    static Stack<Character> left, right;
    static BufferedReader br;
    static StringTokenizer st;
    static StringBuilder sb;

    public static void main(String[] args) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        left = new Stack<>();
        right = new Stack<>();

        input = br.readLine();
        M = Integer.parseInt(br.readLine());

        // 커서가 문장의 맨 뒤에서 시작 -> 왼쪽 스택에 입력받은 문자열을 넣어줌
        for (int i = 0; i < input.length(); i++) {
            left.push(input.charAt(i));
        }

        for (int m = 0; m < M; m++) {
            st = new StringTokenizer(br.readLine());
            char c = st.nextToken().charAt(0);

            if (c == 'L') {
                if (!left.isEmpty()) {
                    right.push(left.pop());
                }
            } else if (c == 'D') {
                if (!right.isEmpty()) {
                    left.push(right.pop());
                }
            } else if (c == 'B') {
                if (!left.isEmpty()) {
                    left.pop();
                }
            } else if (c == 'P') {
                left.push(st.nextToken().charAt(0));
            }
        }

        // 왼쪽 스택의 데이터들을 모두 오른쪽으로 옮긴 후 오른쪽의 내용을 출력해야함
        // 스택은 LIFO 구조이기 때문
        while (!left.isEmpty()) {
            right.push(left.pop());
        }

        while (!right.isEmpty()) {
            sb.append(right.pop());
        }

        System.out.println(sb);
    }
}

📄 해설

접근

• LinkedList 로 구현한 코드는 시간초과 발생 -> Stack 사용하여 해결 (Stack의 Push와 Pop 연산은 O(1) 이므로 더 빠름
• 두 개의 스택을 준비하여, 커서를 대체함
• 시작 커서가 문자열의 맨 뒤에 위치하므로, 왼쪽 스택에 모든 문자를 Push 하고 명령어에 따라 처리
• 이후 스택이 LIFO 구조인 것을 감안하여, 왼쪽 스택의 모든 원소를 오른쪽에 옮기고 전부다 Pop을 통해 출력

과정

• Character 를 담는 스택을 두 개 사용 -> 커서 대체
• 커서가 문장의 맨 뒤에서 시작하므로, 왼쪽 스택에 입력받은 문자열을 모두 넣어줌
• 이후 다음과 같은 과정을 통해 명령어 처리
  • 커서 왼쪽 이동(L) : 왼쪽 스택의 Top을 오른쪽 스택에 Push
  • 커서 오른쪽 이동(D) : 오른쪽 스택의 Top을 왼쪽 스택에 Push
  • 커서 왼쪽 문자 삭제(B) : 왼쪽 스택에서 Pop
  • 커서 왼쪽 문자 추가(P) : 왼쪽 스택에 Push
• 명령 수행이 끝났으면, 왼쪽 스택의 모든 원소를 오른쪽 스택에 담은 후, 전부 다 Pop 하면서 출력