1406.에디터

문제

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

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

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

안녕하세

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

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

입력

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

출력

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.3 초 (하단 참고)	512 MB	108021	30050	20095	26.527%

https://www.acmicpc.net/problem/1406

풀이

코드

1번째 시도

public class 에디터 {  

    public static void main(String[] args) throws IOException {  

        Scanner sc = new Scanner(System.in);  
        List<Character> list = new ArrayList<>();  

        String str = sc.nextLine(); //입력 1번줄을 받아온다.  

        int cursor = 1; //커서를 선언  

        for (int i = 0; i < str.length(); i++) {  
            list.add(str.charAt(i)); //리스트에 str을 한글자씩 넣는다.  
        }  

        cursor = list.size() + 1; //커서의 위치를 잡는다.  

        int M = sc.nextInt(); //입력할 명령어의 개수  

        for (int i = 0; i < M; i++) { //명령어 개수만큼 반복  

            String command = sc.nextLine();  
            char c = command.charAt(0);  
            switch (c) {  
                case 'P':  
                    char ch = command.charAt(2);  
                    list.add(cursor - 1, ch); //커서는 1부터 시작 하니까 1빼준다.  
                    cursor += 1;  

                    break;  

                case 'L':  
                    if (cursor > 1) {  
                        cursor -= 1;  
                    }  
                    break;  

                case 'D':  
                    if (cursor < list.size() + 1) {  
                        cursor += 1;  
                    }  
                    break;  

                case 'B':  

                    if(cursor > 1){  
                        list.remove(cursor-2);  
                        cursor -= 1;  
                    }  
                    break;  
            }  
        }  
        list.forEach(System.out::println);
        bw.flush();  
        bw.close();  
    }  
}

ArrayList로 구현하고, sout으로 출력하니 에러가 발생하였다. 그래서 방법을 변경해보았다.

2번째 시도

import java.io.*;  
import java.util.ArrayList;  
import java.util.List;  
import java.util.Scanner;  

public class 에디터 {  

    public static void main(String[] args) throws IOException {  

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));  
        List<Character> list = new ArrayList<>();  

        String str = br.readLine(); //입력 1번줄을 받아온다.  

        int cursor = 1; //커서를 선언  

        for (int i = 0; i < str.length(); i++) {  
            list.add(str.charAt(i)); //리스트에 str을 한글자씩 넣는다.  
        }  

        cursor = list.size() + 1; //커서의 위치를 잡는다.  

        int M = Integer.parseInt(br.readLine()); //입력할 명령어의 개수  

        for (int i = 0; i < M; i++) { //명령어 개수만큼 반복  

            String command = br.readLine();  
            char c = command.charAt(0);  
            switch (c) {  
                case 'P':  
                    char ch = command.charAt(2);  
                    list.add(cursor - 1, ch); //커서는 1부터 시작 하니까 1빼준다.  
                    cursor += 1;  

                    break;  

                case 'L':  
                    if (cursor > 1) {  
                        cursor -= 1;  
                    }  
                    break;  

                case 'D':  
                    if (cursor < list.size() + 1) {  
                        cursor += 1;  
                    }  
                    break;  

                case 'B':  

                    if(cursor > 1){  
                        list.remove(cursor-2);  
                        cursor -= 1;  
                    }  
                    break;  
            }  
        }  

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

입출력 방식을 BufferedReader / BufferedWriter로 변경 -> 에러 발생

문제를 생각해보면 ArrayList의 사용이 문제인것이다. 이문제는 삽입/ 삭제에 빠른 처리를 요구하고 있으므로 ArrayList의 사용은 불리하다.

답을 처음 작성했을 때, 코드 1처럼 작성을 했다. 문자 입력에 따라 index값을 변화시켜 커서를 움직이는 식으로 했다. 그러나 그렇게 하게 되면, 문자를 삭제하고 list안에서 재배열될 때 O(n)이 나오게 되고, 이것을 반복하게 되면 O(n^2)로 총 명령어가 500,000개 이므로 500,000^2가 되어 시간 초과가 나온다.

그래서 stringbuilder도 사용했지만, 계속해서 시간 초과가 나와 힌트를 얻기 위해 구글링을 했다.

시간 초과를 피하기 위해서 사용한 방법은 왼쪽 스택, 오른쪽 스택을 구현하는 것이었다. 스택에서의 push, pop은 시간 복잡도가 O(1)이어서 n번 반복하면 O(n)이 되기 때문에 시간 초과가 나오지 않는다.

솔직하게 힌트를 보지 않았다면 이 문제는 풀 수 없었을 것 같다. 왼쪽 스택, 오른쪽 스택을 구분하여 문제를 푸는 것이 정말 기발하다고 생각했다. 그리고, index값을 변화시켜 커서를 움직이면 O(n)이 사용된다는 것도 알게 되었다.

그래서 스택을 사용하여 문제를 풀었는데도 시간 초과가 나왔다. 마지막에 StringBuilder를 사용하니 문제가 맞았다.

이 점을 보고, stringbuilder가 println보다 빠른 출력을 하게 됨을 알 수 있었다.

이 문제를 해결하기 위해 여러 질문들과 다른 사람들의 포스트를 찾아보았다.

처음 구현한 방법에서는 index 변수를 이용해 커서의 위치를 다루었고, L/D/B/P 시 LinkedList가 커서의 위치, 즉 해당하는 인덱스를 찾고 삽입/삭제가 처리되는 방식이었다.

하지만 이처럼 위치를 찾아가지 말고 문제의 '커서'처럼 해당하는 위치에 계속 있으면서 삽입/삭제를 처리할 수 있게 하는 방법을 찾았다.

그 방법이 바로 ListIterator의 사용이다!

그리고 LinkedList를 사용해야 한다. 이유는 아래에 첨부한다

ArrayList와 LinkedList의 차이
https://dev-coco.tistory.com/19

3번째 시도

package 기초1.Day02.정해영;  

import java.io.*;  
import java.util.ArrayList;  
import java.util.LinkedList;  
import java.util.List;  
import java.util.ListIterator;  

public class 에디터 {  

    public static void main(String[] args) throws IOException {  

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));  
        List<Character> list = new LinkedList<>();  

        String str = br.readLine(); //입력 1번줄을 받아온다.  

        for (int i = 0; i < str.length(); i++) {  
            list.add(str.charAt(i)); //리스트에 str을 한글자씩 넣는다.  
        }  

        int M = Integer.parseInt(br.readLine()); //입력할 명령어의 개수  

        //iterator메서드 호출.  
        ListIterator<Character> iterator = list.listIterator();  

        //처음에 커서가 문장의 맨뒤에 있어야 하므로 커서를 맨뒤로 이동시킨다.  
        while (iterator.hasNext()){  
            iterator.next();  
        }  

        for (int i = 0; i < M; i++) { //명령어 개수만큼 반복  

            String command = br.readLine();  
            char c = command.charAt(0);  
            switch (c) {  
                case 'P':  
                    char ch = command.charAt(2);  
                    iterator.add(ch);  

                    break;  

                case 'L':  
                    if (iterator.hasPrevious()) {  
                        iterator.previous();  
                    }  
                    break;  

                case 'D':  
                    if (iterator.hasNext()) {  
                        iterator.next();  
                    }  
                    break;  

                case 'B':  

                    if(iterator.hasPrevious()){  
                        iterator.previous();  
                        iterator.remove();  
                    }  
                    break;  
            }  
        }  

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

성공...!

https://minhamina.tistory.com/17
https://hianna.tistory.com/620 리스트 중간에 값추가
https://st-lab.tistory.com/92?category=830901 자바 스캐너 클래스 https://h-apple11.tistory.com/32
https://st-lab.tistory.com/41 자바입력 뜯어보기