2022.02.15 52일차

백준 1406번 (에디터)

문제

한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.

이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.

이 편집기가 지원하는 명령어는 다음과 같다.

L	커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)
D	커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)
B	커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨)

삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임
P $ $라는 문자를 커서 왼쪽에 추가함
초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.

나의 풀이

1. 시간복잡도 유심히 생각하기, 스택 두개 활용
2. index를 활용해서 cursor를 위치값 고려하면 시간복잡도O(N)
3. 스택의 pop과 push만을 활용해서 시간복잡도O(1)가 되도록 하기
4. 출력 또한 StringBuilder로 모아서 출력

import java.io.*;
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));

        String s = br.readLine();

        int N = Integer.parseInt(br.readLine());
        Stack<String> lStack = new Stack<>();
        Stack<String> rStack = new Stack<>();

        for (int x = 0; x < s.length(); x++) {
            lStack.push(s.substring(x, x + 1));
        }

        for (int i =0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            switch (st.nextToken()) {
                case "L":
                    if (!lStack.isEmpty()) {
                        rStack.push(lStack.pop());
                    }
                    break;
                case "D":
                    if (!rStack.isEmpty()) {
                        lStack.push(rStack.pop());
                    }
                    break;
                case "B":
                    if (!lStack.isEmpty()) {
                        lStack.pop();
                    }
                    break;
                case "P":
                    lStack.push(st.nextToken());
                    break;
            }
        }

        while (!lStack.isEmpty()) {
            rStack.push(lStack.pop());
        }

        StringBuilder sb = new StringBuilder();

        while (!rStack.isEmpty()) {
            sb.append(rStack.pop());
        }
        System.out.println(sb);
    }
}

생각하기

• 시간복잡도와 스택에 대해서 연습할 수 있는 문제
• 스택을 두개 활용해서 접근하는 방법 배움