백준 1406 - 에디터 [Java]

문제

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

---

❌ 코드 1 (시간 초과)

import java.util.*;
import java.io.*;

public class Main {
    static LinkedList<Character> ll = new LinkedList<>();

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

        String str = bf.readLine();
        int N = str.length();
        for (int i = 0; i < N; i++) {
            ll.addLast(str.charAt(i));
        }

        int M = Integer.parseInt(bf.readLine());
        int cursor = N;
        for (int i = 0; i < M; i++) {
            String[] inputs = bf.readLine().split(" ");
            if (inputs[0].equals("L") && cursor > 0) {
                cursor--;
            } else if (inputs[0].equals("D") && cursor < ll.size()) {
                cursor++;
            } else if (inputs[0].equals("B") && cursor > 0) {
                ll.remove(--cursor);
            } else if (inputs[0].equals("P")){
                ll.add(cursor++, inputs[1].charAt(0));
            }
        }

        for (char c: ll) {
            bw.write(c);
        }

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

• LinkedList에 인덱스 위치(cursor)를 지정해서 삭제/삽입을 하고 있다.
• 그런데 LinkedList는 구조 상 get(i), add(i, x), remove(i)와 같이 인덱스 기반 접근이 O(i)가 된다(처음부터 순차적으로 내려가므로).
• 따라서 최악의 경우 시간 복잡도가 O(N × M)이 된다.

⭕ 코드 2

import java.util.*;
import java.io.*;

public class Main {
    static LinkedList<Character> ll = new LinkedList<>();

    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();
        for (int i = 0; i < str.length(); i++) {
            ll.add(str.charAt(i));
        }

        ListIterator<Character> li = ll.listIterator(ll.size());
        int M = Integer.parseInt(br.readLine());
        for (int i = 0; i < M; i++) {
            String[] inputs= br.readLine().split(" ");
            if (inputs[0].equals("L") && li.hasPrevious()) {
                li.previous();
            } else if (inputs[0].equals("D") && li.hasNext()) {
                li.next();
            } else if (inputs[0].equals("B") && li.hasPrevious()) {
                li.previous();
                li.remove();
            } else if (inputs[0].equals("P")) {
                li.add(inputs[1].charAt(0));
            }
        }

        for (char c: ll) {
            bw.write(c);
        }

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

• int cursor 대신 ListIterator li를 사용했다.
  • ListIterator는 리스트를 앞뒤로 와리가리 치면서 현재 위치에서 바로 삽입/삭제까지 할 수 있는 커서 도구다.
  • previous() / next() : 커서를 왼쪽/오른쪽으로 이동하면서 문자 하나를 꺼냄
  • hasPrevious() / hasNext() : 왼쪽/오른쪽에 문자가 있는지 확인
  • add(x) : 현재 커서 위치에 바로 삽입
  • remove() : 방금 previous()나 next()로 꺼낸 그 원소를 삭제
• LinkedList에서 add(i, x), remove(i)는 i번째까지 찾아가느라 느림
• ListIterator의 add/remove는 이미 그 위치에 서 있으니까 빠름 ≈ O(1)