[Algorithm/Baekjoon] 에디터 - 1406 (S2/JAVA)

📑문제링크

1406번: 에디터

💻코드

import java.io.*;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;

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));
        Stack<Character> leftStack = new Stack<>();
        Stack<Character> rightStack = new Stack<>();

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

        int M = Integer.parseInt(br.readLine());
        for (int i = 0; i < M; i++) {
            String orderLine = br.readLine();

            char order = orderLine.charAt(0);
            if (order == 'L') {// 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)
                if(!leftStack.isEmpty()) rightStack.push(leftStack.pop());
            } else if (order == 'D') {// 커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)
                if(!rightStack.isEmpty()) leftStack.push(rightStack.pop());
            } else if (order == 'B') {// 커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨)
                if(!leftStack.isEmpty()) leftStack.pop();
            } else if (order == 'P') {// $라는 문자를 커서 왼쪽에 추가함
                leftStack.push(orderLine.charAt(2));
            }
        }

        while(!leftStack.isEmpty()){
            rightStack.push(leftStack.pop());
        }
        while(!rightStack.isEmpty()){
            bw.write(rightStack.pop());
        }
        
        br.close();
        bw.close();
    }
}

⏳회고

• 문제를 보고 문자열 중간에 삽입, 삭제, 이동이 일어나 List를 사용하여 풀이하였다. List를 탐색하는데 O(N) 시간이 들어서 시간초과가 발생했다.
• 삽입, 삭제, 이동하는데 시간을 O(1)로 줄이기 위해서 Stack으로 풀이하였다.