1406. 에디터

1406. 에디터

제출일 : 2020-06-28

문제 풀이 시간 : 1H

난이도 : Silver III

---

:link: 문제 link

문제

한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 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

문제 풀이 접근

문제를 처음 풀때 LinkedList를 이용하여 문제를 풀었다. 코드 1을 작성했고 그 결과 시간초과가 발생하였다.

코드 1

언어 : JAVA

결과 : 시간초과

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String str = sc.next();
        LinkedList<Character> list = new LinkedList<>();

        for (int i = 0; i < str.length(); i++) {
            list.add(str.charAt(i));
        }
        int cursor = str.length();
        int M = sc.nextInt(); // 명령어의 개수

        for (int k = 0; k < M; k++) {
            char cmd = sc.next().charAt(0);
            switch (cmd) {
                case 'L':
                    if (cursor != 0)
                        cursor--;
                    break;
                case 'D':
                    if (cursor != list.size())
                        cursor++;
                    break;
                case 'B':
                    if (cursor != 0)
                        list.remove(--cursor);
                    break;
                case 'P':
                    char c = sc.next().charAt(0);
                    list.add(cursor++, c);
                    break;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (Character c : list) {
            sb.append(c);
        }
        System.out.println(sb);
    }
}

처음 Scanner로 입력을 받고 System.out.println()으로 출력을 했다. 시간초과가 발생해 빠른 BufferedReader과 BufferedWriter로 입출력 방식을 변경했지만 결과는 시간초과가 발생했다.

코드 2

언어 : JAVA

결과 : 시간초과

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.StringTokenizer;

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

        LinkedList<Character> list = new LinkedList<>();
        for (int i = 0; i < str.length(); i++) {
            list.add(str.charAt(i));
        }
        int cursor = str.length();
        int M = Integer.parseInt(br.readLine()); // 명령어의 개수

        for (int k = 0; k < M; k++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            char cmd = st.nextToken().charAt(0);
            switch (cmd) {
                case 'L':
                    if (cursor != 0)
                        cursor--;
                    break;
                case 'D':
                    if (cursor != list.size())
                        cursor++;
                    break;
                case 'B':
                    if (cursor != 0)
                        list.remove(--cursor);
                    break;
                case 'P':
                    char c = st.nextToken().charAt(0);
                    list.add(cursor++, c);
                    break;
            }
        }

        for (Character c : list) {
            bw.write(c);
        }
        bw.flush();
    }
}

LinkedList는 ArrayList에 비해 임시 배열을 생성하지 않아 삽입/삭제가 더 유리한 장점을 가지고 있다.

하지만 N번째에 값을 삽입하거나 삭제하려면 인덱스를 통한 접근을 할 수 없기에 N번의 탐색과정이 필요하다.

이 시간을 줄여야 했기에 Iterator를 사용하여 문제를 해결했다.

ListIterator는 Iterator를 상속한 인터페이스다.

Iterator의 단방향 탐색과 달리 양방향 탐색이 가능하다.

그렇기에 이 문제처럼 양방향으로 이동하면서 수정하기에 효율적이다.

코드 3

언어 : JAVA

메모리 : 115812 kb

실행 시간 : 668 ms

결과 : 맞았습니다!!

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.StringTokenizer;

public class Silver3_1406_에디터 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String str = br.readLine();

        LinkedList<Character> list = new LinkedList<>();
        for (int i = 0; i < str.length(); i++) {
            list.add(str.charAt(i));
        }
        ListIterator<Character> iter = list.listIterator(list.size());
        int M = Integer.parseInt(br.readLine());

        for (int k = 0; k < M; k++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            switch (st.nextToken()) {
                case "L":
                    if (iter.hasPrevious())
                        iter.previous();
                    break;
                case "D":
                    if (iter.hasNext())
                        iter.next();
                    break;
                case "B":
                    if (iter.hasPrevious()) {
                        iter.previous();
                        iter.remove();
                    }
                    break;
                case "P":
                    iter.add(st.nextToken().charAt(0));
                    break;
            }
        }

        for (Character c : list) {
            bw.write(c);
        }
        bw.flush();
    }
}

문제 해결을 위해 블로그의 글들을 보니 대부분 2개의 스택을 이용하여 구현하여 문제를 해결했다. 스텍을 활용한 문제풀이의 핵심 아이디어는 왼쪽과 오른쪽 스택을 구분지어 커서의 위치를 항상 왼쪽 Top에 위치하여 문제를 푸는 것이다.

코드 4

언어 : JAVA

메모리 : 119188 kb

실행 시간 : 804 ms

결과 : 맞았습니다!!

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

public class Silver3_1406_에디터_ver2 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String str = br.readLine();

        Stack<Character> left = new Stack<>();
        Stack<Character> right = new Stack<>();
        for (int i = 0; i < str.length(); i++) {
            left.add(str.charAt(i));
        }

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

        for (int k = 0; k < M; k++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            switch (st.nextToken()) {
                case "L":
                    if (!left.isEmpty())
                        right.push(left.pop());
                    break;
                case "D":
                    if (!right.isEmpty())
                        left.push(right.pop());
                    break;
                case "B":
                    if (!left.isEmpty())
                        left.pop();
                    break;
                case "P":
                    left.push(st.nextToken().charAt(0));
                    break;
            }
        }

        while (!left.isEmpty()) {
            right.push(left.pop());
        }
        while (!right.isEmpty()) {
            bw.write(right.pop());
        }

        bw.flush();
    }
}

📚 Reference :books:

https://minhamina.tistory.com/17