[백준][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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        int idx = str.length(); //커서 위치
        List<Character> list = new LinkedList();

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

        while(m-->0){
            String cmd = br.readLine();
            if(cmd.startsWith("P")){
                char ch = cmd.split(" ")[1].charAt(0);
                list.add(idx, ch);
                idx++;
            }else if(cmd.equals("B")){
                if(idx-1 >= 0){
                    list.remove(idx-1);
                    idx--;
                }
            }else if(cmd.equals("L")){
                if(idx-1 >= 0){
                    idx--;
                }
            }else if(cmd.equals("D")){
                if(idx+1<= list.size()){
                    idx++;
                }
            }
        }
        for(char ch: list){
            bw.write(ch);
        }
        bw.flush();
        bw.close();
    }
}

틀린 이유

ArrayList와 달리 삽입/삭제시 임시배열을 생성하여 밀어내는 식으로 복사하는 방식이아닌
이전과 다음요소의 정보를 활용하여 삽입/삭제를 하기때문에 LinkedList를 선택했었다.

하지만 시간초과가 일어났다.

위 코드에서 LinkedList의 원하는 위치(인덱스)의 삽입/삭제가 이루어지고 있다.
해당 위치까지 찾아가는 작업이 최악의 경우 O(n)의 복잡도를 가지게된다.
즉, 삽입/삭제시 그 인덱스에 바로 접근하는 것이 아니다.
문제의 크기 n은 최대 60만까지 될 수 있기때문에
효율적이지 못하고시간초과의 원인이라고 생각한다.

문제 해결 방법이 떠오르지 않아 구글링을 활용했다.
출처: https://mygumi.tistory.com/62

위 작성자는 대체로 ListIterator를 활용하여 해결하는 방법을 제시했다.
Iterator를 상속한 인터페이스로서 List에 포함된 모든 객체를 양방향으로 탐색하며 객체를 조작하는 방법을 제공한다.
문제의 커서처럼 해당하는 위치에 있으면서 삽입/삭제를 처리할 수 있다.

다른 새로운 방법

이 문제는 stack을 활용해서 해결할 수도 있다.
커서를 기준으로 커서의 왼쪽 스택(left)와 오른쪽 스택(right)로 나누어 풀수있다.

1) L연산
왼쪽 스택의 top데이터를 오른쪽 스택으로 push한다.
복잡도 : O(1)

2) D연산
1과 마찬가지다.

3) B연산
왼쪽 스택 pop()
복잡도 : O(1)

4) P연산 왼쪽 스택에 push
복잡도 : O(1)

다른 풀이

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        Stack<Character> left = new Stack<Character>();
        Stack<Character> right = new Stack<Character>();
        for (int i=0; i<s.length(); i++) {
            left.push(s.charAt(i));
        }
        int m = Integer.parseInt(br.readLine());
        while (m-- > 0) {
            String[] line = br.readLine().split(" ");
            char what = line[0].charAt(0);
            if (what == 'L') {
                if (!left.empty()) {
                    right.push(left.pop());
                }
            } else if (what == 'D') {
                if (!right.empty()) {
                    left.push(right.pop());
                }
            } else if (what == 'P') {
                char c = line[1].charAt(0);
                left.push(c);
            } else if (what == 'B') {
                if (!left.empty()) {
                    left.pop();
                }
            }
        }
        while (!left.empty()) {
            right.push(left.pop());
        }
        StringBuilder sb = new StringBuilder();
        while (!right.empty()) {
            sb.append(right.pop());
        }
        System.out.println(sb);
    }
}

느낀점 키워드

1. LinkedList에서 remove와 add는 리스트의 처음부터 끝까지 탐색한다는 걸 잊지말자. O(n)의 시간이 걸린다.
2. ListIterator을 활용해서 풀수도있다.
3. 커서기준 왼쪽,오른쪽 stack을 나누어 LIFO성질을 활용한 방법