[Baekjoon/Programmers] 1406 에디터

1406 에디터문제 해결 과정.

Stack이나 LinkedList를 사용하려 했으나 특정 인덱스에 있는 문자를 삭제할 때 번거로울 것 같아서 StringBuilder를 사용해서 풀어봤다.

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

public class Main {

    public static void main(String[] args)  throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringBuilder editor = new StringBuilder(br.readLine());
        int cursor = editor.length();

        int n = Integer.parseInt(br.readLine());
        for (int i=0; i<n; i++) {
            String[] cmd = br.readLine().split(" ");

            switch (cmd[0]) {
                case "L" :
                    if (cursor > 0) cursor--;
                    break;
                case "D" :
                    if (cursor < editor.length())
                        cursor++;
                    break;
                case "B" :
                    if (cursor > 0) {
                        editor.deleteCharAt(cursor-1);
                        cursor--;
                    }
                    break;

                case "P" :
                    editor.insert(cursor, cmd[1]);
                    if (cursor < editor.length()) cursor++;
                    break;
            }
        }
        System.out.println(editor);
    }
}

결과는 시간초과였다. 요소의 위치를 접근할 때 시간 복잡도가 O(N)이 아닌 O(1)이 되어야 된다는 게 문제의 핵심이라는데, 어쨌든 링크드리스트에서 ListIterator를 사용해 주어야 한다고 한다. (Iterator는 역방향 조회가 불가능) 코드 수정 중 **ConcurrentModificationException** 오류가 발생했는데, 이는 컬렉션 순회와 동시에 컬렉션의 내용을 수정할 때 발생하는 오류라고 한다. LinkedList인 editor에 변경을 가하는 것이 문제여서 ListIterator인 cursor에 변경을 가했더니 해결되었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.ListIterator;

public class Main {

    public static void main(String[] args)  throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        LinkedList<Character> editor = new LinkedList<Character>();

        for (char ch: br.readLine().toCharArray()) {
            editor.add(ch);
        }
        ListIterator<Character> cursor = editor.listIterator();
        while(cursor.hasNext()) {
            cursor.next();
        }

        int n = Integer.parseInt(br.readLine());
        for (int i=0; i<n; i++) {
            String[] cmd = br.readLine().split(" ");

            switch (cmd[0]) {
                case "L" :
                    if (cursor.hasPrevious()) cursor.previous();
                    break;

                case "D" :
                    if (cursor.hasNext()) cursor.next();
                    break;

                case "B" :
                    if (cursor.hasPrevious()) {
                        cursor.previous();
                        cursor.remove();
                    }
                    break;

                case "P" :
                    Character input = cmd[1].charAt(0);
                    cursor.add(input);
                    break;
            }
        }

        for (Character ch : editor) {
            System.out.print(ch);
        }
    }
}

그러나 역시나 시간초과였다… 질문게시판을 찾아보던 중에 String은 많이 무겁다는 답변을 읽고 타입을 모두 char로 바꿔주었는데 55%정도까지 채점되다가 또 시간초과………. 도대체 뭐가 문제인 건데… 머리를 싸매다가 BufferedWriter를 이용해 출력하니 해결되었다.. 제법 허무한 결말

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

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));

        LinkedList<Character> editor = new LinkedList<Character>();

        for (char ch: br.readLine().toCharArray()) {
            editor.add(ch);
        }
        ListIterator<Character> cursor = editor.listIterator();
        while(cursor.hasNext()) {
            cursor.next();
        }

        int n = Integer.parseInt(br.readLine());
        for (int i=0; i<n; i++) {
            char[] cmd = br.readLine().toCharArray();

            switch (cmd[0]) {
                case 'L' :
                    if (cursor.hasPrevious()) cursor.previous();
                    break;

                case 'D' :
                    if (cursor.hasNext()) cursor.next();
                    break;

                case 'B' :
                    if (cursor.hasPrevious()) {
                        cursor.previous();
                        cursor.remove();
                    }
                    break;

                case 'P' :
                    char input = cmd[2];
                    cursor.add(input);
                    break;
            }
        }

        for (Character ch : editor) {
            bw.write(ch);
        }

        bw.flush();
        bw.close();
    }
}

++ 천재만재 순위권 선생님들 코드를 보다 알게 된 것

ListIterator<Character> cursor = editor.listIterator();
while(cursor.hasNext()) {
    cursor.next();
} 

커서를 입력받은 문자열 제일 뒤에 위치시키기 위해 while문을 돌렸었는데,

java ListIterator<Character> cursor = editor.listIterator(editor.size());

로 더 간결하게 할 수 있다! 자체적으로 커서나 에디터를 만드시는 분들도 계시는 걸 보고 또 벽을 느끼고요…