백준 1406 에디터

• 틀렸던 코드

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

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

        // 최대 60만
        /*
         * 모든 명령어를 수행하고 편집기에 입력되어있는 문자열은?
         * O(n)
         * */
        LinkedList<String> list = new LinkedList<>();
        String data = br.readLine();
        String[] dataArr = data.split("");

        for (int i = 0; i < dataArr.length; i++) {
            list.add(i, dataArr[i]);
        }

        int n = Integer.parseInt(br.readLine());

        int size = list.size();
        int cursor = size;

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String operator = st.nextToken();

            if (operator.equals("P")) {
                String word = st.nextToken();

                list.add(cursor, word);
                size++;
                cursor++;
                continue;
            }
            if (operator.equals("L")) {
                if (cursor == 0) {
                    continue;
                }
                cursor--;
                continue;
            }
            if (operator.equals("D")) {
                if (cursor == size) {
                    continue;
                }
                cursor++;
                continue;
            }
            if (operator.equals("B")) {
                if (cursor == 0) {
                    continue;
                }
                size--;
                list.remove(cursor - 1);
                cursor--;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (String s : list) {
            sb.append(s);
        }

        System.out.print(sb);
    }
}

처음에는. 중간에서 삽입 삭제를 하기 편한 linkedlist를 사용했다.
그러나

동작	ArrayList	LinkedList
임의 인덱스 접근 (get(i))	O(1)	O(n)(i번째까지 이동 필요)
중간 삽입/삭제 (add(i), remove(i))	O(n) (뒤 요소 밀기)	O(n) (i까지 이동 후 포인터 연결)
앞/뒤 삽입 (addFirst, addLast)	O(1)	O(1)
Iterator 삽입/삭제	O(1)	O(1)

자료구조 시간 복잡도를 모르고 있었다. 중간 삽입 삭제가 O(n)이 걸린다. 그래서 이 문제는 O(n) 수준으로 풀어야되는데, O(n^2) 이상으로 풀고 있었던 것이다.

해결 방법(1)

1. listIterator 사용

항목	LinkedList	ListIterator
내부 구조	이중 연결 리스트 (prev / value / next)	연결 리스트의 노드를 직접 참조하는 커서
위치 접근 방식	인덱스로 접근 → 노드 탐색 필요	현재 커서 노드를 기억하므로 탐색 없음
주요 목적	자료 저장	리스트 순회 + 편집
양방향 이동	가능하지만 get(i)는 O(N)	next(), previous() 모두 O(1)

연산	LinkedList (인덱스 기반)	LinkedList + ListIterator
get(i)	O(N)	O(1) (커서가 이미 위치를 알고 있음)
add(index, x)	O(N) (index까지 탐색 필요)	O(1)
remove(index)	O(N)	O(1)
이전 요소 이동	O(N) → get(i-1)	previous() → O(1)
다음 요소 이동	O(N) → get(i+1)	next() → O(1)

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        LinkedList<Character> list = new LinkedList<>();
        String data = br.readLine();

        for (char d : data.toCharArray()) {
            list.add(d);
        }

        int n = Integer.parseInt(br.readLine());
        ListIterator<Character> li = list.listIterator(list.size());

        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            char operator = line.charAt(0);

            if (operator == 'P') {
                char x = line.charAt(2);
                li.add(x);
                continue;
            }
            if (operator == 'L') {
                if (!li.hasPrevious()) {
                    continue;
                }
                li.previous();
                continue;
            }
            if (operator == 'D') {
                if (!li.hasNext()) {
                    continue;
                }
                li.next();
                continue;
            }
            if (operator == 'B') {
                if (!li.hasPrevious()) {
                    continue;
                }
                li.previous();
                li.remove();
            }
        }

        StringBuilder sb = new StringBuilder();
        for (char c : list) {
            sb.append(c);
        }
        System.out.print(sb.toString());
    }
}

해결 방법(2)

deque 2개를 이용해서 left의 마지막은 cursor 위치로 고정 -> O(n) 수준으로 풀이 가능

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

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

        Deque<Character> left = new ArrayDeque<>();
        Deque<Character> right = new ArrayDeque<>();

        String data = br.readLine();

        for (char d : data.toCharArray()) {
            left.add(d);
        }

        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            char operator = line.charAt(0);

            if (operator == 'P') {
                char x = line.charAt(2);
                left.add(x);
                continue;
            }
            if (operator == 'L') {
                if (left.isEmpty()) {
                    continue;
                }
                right.addFirst(left.removeLast());
                continue;
            }
            if (operator == 'D') {
                if (right.isEmpty()) {
                    continue;
                }
                left.addLast(right.removeFirst());
                continue;
            }
            if (operator == 'B') {
                if (left.isEmpty()) {
                    continue;
                }
                left.removeLast();
            }
        }

        StringBuilder sb = new StringBuilder();

        while (!left.isEmpty()) {
            sb.append(left.remove());
        }
        while (!right.isEmpty()) {
            sb.append(right.remove());
        }
        System.out.print(sb);
    }
}

1406 에디터