[백준 알고리즘] 1406번 에디터(Java) 문제 풀이

문제

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

1406번: 에디터

문제에 대한 이해

주어진 문제의 조건에 따라서 입출력을 하면 되는 문제였다. 다만 시간복잡도를 참고하였을 때, 자료구조에 굉장히 많이 고민을 해야했다.

 

어떻게 풀 것인가?

이 문제의 경우 처음에는 LinkedList로 풀었다가 크게 얘를 먹었다. 시간초과가 계속해서 발생했고, 해결법을 찾지못해서 다른 분의 블로그를 참조하였다.

https://minhamina.tistory.com/17

[백준 - Java] 1406번 : 에디터

ListIterator를 사용하였고, ListIterator는 Iterator를 상속한 인터페이스다. Iterator의 단방향 탐색과 달리 양방향 탐색이 가능하다.

그렇기에 이 문제처럼 양방향으로 이동하면서 수정하기에 효율적이다. 라는 것을 알게되었다.

시간복잡도

양방향으로 이동하며 수정할 수 있고, 또한 탐색이 가능하다.

시간복잡도는 O(logN)라고 생각한다.

공간복잡도

ListIterator의 크기만 고려했음으로 O(N)이라고 생각한다.

풀면서 놓쳤던점

자료구조에 대해서 애를 많이 먹었다.

이 문제를 통해 얻어갈 것

https://minhamina.tistory.com/18

[Java] Iterator / ListIterator

Listiterator라고 하는 새로운 자료구조에 대하여 학습을 할 수 있었다.

다만 완전한 체화를 위해서는 관련 문제를 더 풀어봐야할 것 같다.

내 코드 

package baekjoon2.BJ_1406;

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

// 백준알고리즘 1406번 에디터

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

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

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

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

        //iterator 메소드 호출
        ListIterator<Character> iter = list.listIterator();
        //처음 커서는 문장의 맨 뒤에 있어야하기 때문에 커서를 맨뒤로 이동시켜줌 (ex. abc|)
        while (iter.hasNext()) {
            iter.next();
        }

        for (int i = 0; i < M; i++) {
            String command = br.readLine();
            char c = command.charAt(0);
            switch (c) {
                case 'L':
                    if (iter.hasPrevious())
                        iter.previous();

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

                    break;
                case 'B':
                    //remove()는 next()나 previous()에 의해 반환된 가장 마지막 요소를 리스트에서 제거함
                    if (iter.hasPrevious()) {
                        iter.previous();
                        iter.remove();
                    }
                    break;
                case 'P':
                    char t = command.charAt(2);
                    iter.add(t);

                    break;
                default:
                    break;
            }
        }
        for (Character chr : list) {
            bw.write(chr);
        }

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