백준 1406번 에디터 Java

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

문제

---

생각하기

---

• 문자열 문제이다.

• 커서 관리인데 이런 유형의 문제는 또 처음 보는 듯

• 커서 관리 문제는 그렇게 어렵다 치지 않아도 최적화가 필요한 문제라 그게 좀 어려운 것 같다.

동작

이 문제를 풀고 나서 메모리가 너무 많이 사용되어서 뭐가 문제였나 한번 찾아봤다.

    StringTokenizer st = new StringTokenizer(command);
    st.nextToken();

    String s = st.nextToken();
    iter.add(s.charAt(0));
    break;

이렇게 p가 입력됐을 때, StringTokenizer를 사용해서 문자열을 분리했다.

이렇게 나왔고

    char ch = command.charAt(2);
    iter.add(ch);
    break;

그냥 chatAt()을 사용했을 때 와 꽤 많은 차이가 났다.

GPT 말로는 실제로는 큰 차이가 없을 거란다.
그래도 이렇게 2개로 분리가 되는 경우에는 앞으로 StringTokenizer 보다 charAt() 좀 지향하는 걸로 해야겠다.

최적화

처음에 LinkedList<>에서 커서 index 직접 변수로 만들어서 문제풀었는데 이렇게 하니까 관리가 안된다.
바로~ 시간초과 발생 그래서 StringBuilder 사용했는데 이것도 시간초과가 났다

원인

그래서 정답을 그냥 찾아봤는데 LinkedList를 ListIterator 라는 자료구조를 사용해서 풀어야 하는 문제였다.
이런 자료구조는 또 처음 봄..

        LinkedList<Character> list = new LinkedList<>();
        for (char ch : chArr) {
            list.offer(ch);
        }

        ListIterator<Character> iter = list.listIterator();
        while (iter.hasNext()) {
            iter.next(); // 커서를 가장 끝으로 이동
        }

아무튼 ListIterator를 사용해서 커서를 관리할 수 있었다.

근데 똑같이 LinkedList에서 사용하는건데 저게 어떻게 최적화가 되는건지 원리가 궁금했다.

결론은

연산의 시간 복잡도
LinkedList.remove(int index)를 사용할 때, 리스트는 처음부터 index 위치까지 순회해야 합니다. 이는 삭제하려는 요소에 도달하기 위해

$O(n)$ 시간이 소요될 수 있음을 의미합니다. n은 리스트의 길이입니다.
ListIterator.remove()를 사용할 경우, 반복자는 이미 특정 위치에 있습니다. 따라서, 순회 없이 현재 요소를 바로 삭제할 수 있습니다. 이 연산은 $O(1)$ 시간 내에 수행됩니다.

라고 한다.

결과

코드

---

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

public class Main {

    // input
    private static BufferedReader br;

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

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() throws IOException {
        StringBuilder sb = new StringBuilder();

        char[] chArr = br.readLine().toCharArray();
        LinkedList<Character> list = new LinkedList<>();
        for (char ch : chArr) list.offer(ch);

        ListIterator<Character> iter = list.listIterator();
        while (iter.hasNext()) {
            iter.next();
        }

        int M = Integer.parseInt(br.readLine());
        while (M-- > 0) {
            String com = br.readLine();

            switch (com.charAt(0)) {
                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':
                    char ch = com.charAt(2);
                    iter.add(ch);
                    break;
            }
        }

        for (char ch : list) sb.append(ch);
        return sb.toString();
    } // End of solve()
} // End of Main class