[ 자바 ] 백준 1406번 에디터 문제풀이

제목

---

시간제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.3 초	512 MB	101997	28301	18880	26.537%

 

 

 

문제

---

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

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

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

L	커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)
D	커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)
B	커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨) 삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임
P$	$라는 문자를 커서 왼쪽에 추가함

초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.

 

 

입력

---

첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 M(1 ≤ M ≤ 500,000)이 주어진다. 셋째 줄부터 M개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다. 명령어는 위의 네 가지 중 하나의 형태로만 주어진다.

 

 

출력

---

첫째 줄에 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 출력한다.

 

 

예제 입력

abcd
3
P x
L
P y

 

 

 

예제 출력 

abcdyx

 

 

 

문제 풀이

---

문제에서 주어지는 조건에 맞게 임의의 문자열이 주어지면 이후에 입력되는 문자를 일종의 커서 위치로 인식하고 P $의 $를 문자로 취급하여 $에 해당하는 문자를 대입하는 문제다. 따라서 switch 조건문을 활용하여 해당 조건에 바로바로 대입하는 형식으로 코드를 구현하였다.

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

public class EditorEx {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String str = br.readLine();
        int num = Integer.parseInt(br.readLine());
        sb.append(str);

        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < str.length(); i++) {
            stack.add(str.charAt(i));
        }

        int size = stack.size();

        for (int i = 0; i < num; i++) {
            String ldbp = br.readLine();
            char c = ldbp.charAt(0);
            switch(c) {
                case 'L':
                    if(size != 0) {
                        size = size - 1;
                    }
                    break;

                    case 'D':
                    if(size != stack.size()) {
                        size = size + 1;
                    }
                    break;

                    case 'B':
                    if(size != 0) {
                        stack.remove(size-1);
                        size--;
                    }
                    break;
                case 'P':
                    char t = ldbp.charAt(2);
                    stack.add(size, t);
                    size++;

                    break;
                default:
                    break;
            }
        }
        for (Character chr : stack) {
            System.out.print(chr);
        }
    }
}

결과는 '시간초과' stack을 LIFO를 고려하지 않고 문제 풀이만을 고려해서 구현했더니 다음과 같은 결과가 나온 것 같다.

따라서, 검색을 해본 결과 leftStack과 rigthStack으로 이분하여 푸는 방법이 있었다.

 

즉, 양쪽에 스택이 있다고 가정했을 때 초기에는 abcd가 순서대로 leftStack으로 할당된다. 이후에 push되는 문자는 leftStack에 넣어주고 커서가 왼쪽으로 이동하게 된다면 이후의 문자를 rightStack을 pop해준다. 모든 명령어가 처리되면 최종적으로 leftStack의 요소들을 rightStack으로 pop하고 rightStack을 pop하여 출력한다.

 

import java.io.*;
import java.util.Stack;

public class EditorEx {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String str = br.readLine();
        int num = Integer.parseInt(br.readLine());

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

        String[] arr = str.split("");
        for (String s : arr) {
            leftStack.push(s);
        }

        for (int i = 0; i < num; i++) {
            String ldbp = br.readLine();
            char c = ldbp.charAt(0);
            switch(c) {
                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':
                    char t = ldbp.charAt(2);
                    leftStack.push(String.valueOf(t));

                    break;
                default:
                    break;
            }
        }
        while (!leftStack.isEmpty()) {
            rightStack.push(leftStack.pop());
        }
        while (!rightStack.isEmpty()) {
            bw.write(rightStack.pop());
        }
        bw.flush();
        bw.close();
    }
}