1406번 에디터

첫번째 풀이(실패) - LinkedList 사용

삽입과 삭제가 가능해야하므로 LinkedList를 사용해서 풀이를 하였다.
초기에 주어지는 문자열의 길이를 구해서 cursor를 초기화해준다.
-> 문자열의 길이가 아닌 list로 문자열의 각 문자를 넣은 후 list의 크기를 구하여 cursor를 초기화(사실 여기서는 문자열의 길이로 해도 상관 없으나, 아래 명령어가 'D'일 경우는 문자열의 길이로 비교하면 안됨.)
그 후 명령어 개수은 M만큼 반복문을 돌며 명령어에 해당하는 동작을 하도록 코드를 작성하였다.

• 명령어가 'L'일 경우: 현재 cursor가 0이 아니라면 -1을 해준다.

• 명령어가 'D'일 경우: 현재 cursor와 문자열의 길이 list의 길이를 비교 후 cursor가 더 작다면 +1을 해준다. (문자열의 길이와 cursor를 비교하면 안됨. 중간에 문자가 삭제되거나 삽입되는 경우가 있으므로)

• 명령어가 'B'일 경우: cursor - 1에 위치한 list 요소를 제거한다. list.remove(cursor-1)

• 명령어가 'P'일 경우: cursor에 해당하는 위치에 문자를 추가한다. list.add(cursor, add)

package BOJ;

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

public class sol1406 {
    static String init;
    static int M;
    static LinkedList<Character> list;
    static int cursor;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        init = br.readLine();
        list = new LinkedList<>();
        for (int i = 0; i < init.length(); i++) {
            list.add(init.charAt(i));
        }
        cursor = list.size();
        M = Integer.parseInt(br.readLine());
        for (int i = 0; i < M; i++) {
            String command = br.readLine();
            char c = command.charAt(0);
            switch (c) {
                case 'L':
                    if (cursor != 0) cursor -= 1;
                    break;
                case 'D':
                    if (cursor != list.size()) cursor += 1;
                    break;
                case 'B':
                    if (cursor != 0) {
                        list.remove(cursor - 1);
                        cursor--;
                    }
                    break;
                case 'P':
                    char add = command.charAt(2);
                        list.add(cursor, add);
                        cursor++;
                    break;

                default:
                    break;
            }
        }
        for (Character c : list) {
            bw.write(c);
        }
        bw.flush();
        bw.close();
    }
}

시간초과...

LinkedList 자료구조에서 단순히 요소를 삽입하는 과정은 시간복잡도가 O(1)이다.
-> 새로운 노드를 추가하고, 앞 뒤 노드의 참조를 수정만 하면 되기 때문.
하지만 해당 인덱스까지 접근하는 과정이 O(n)의 시간 복잡도를 가진다. 앞에서부터 차례로 접근해야하기 때문.
위 코드의 시간 복잡도는 O(M*N+N)이다.
명령어의 최대 개수가 500,000이고 문자열의 최대 길이가 100,000이므로 해당 코드로는 시간초과가 뜰 수 밖에 없다.

두번째 풀이 - LinkedList 사용 + ListIterator

LinkedList의 index를 찾아 접근하는 과정을 제거해야하기 때문에 첫번째 풀이처럼 cursor(인덱스)를 매번 접근하는 것이 아닌 진짜 커서처럼 계속 위치를 유지하며 삽입/삭제를 처리할 수 있어야한다.

다른 사람들의 풀이를 찾아보니 ListIterator를 사용하였다.

package BOJ;

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

public class sol1406 {
    static String init;
    static int M;
    static LinkedList<Character> list;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        init = br.readLine();
        list = new LinkedList<>();
        for (int i = 0; i < init.length(); i++) {
            list.add(init.charAt(i));
        }
        ListIterator<Character> iter = list.listIterator(list.size()); //iter를 제일 뒤로 옮겨준다.(커서는 초기에 가장 우측에 위차하므로)
        M = Integer.parseInt(br.readLine());
        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':
                    if (iter.hasPrevious()) {
                        iter.previous();
                        iter.remove();
                    }
                    break;
                case 'P':
                    char add = command.charAt(2);
                    iter.add(add);
                    break;

                default:
                    break;
            }
        }
        for (Character c : list) {
            bw.write(c);
        }
        bw.flush();
        bw.close();
    }
}

ListIterator

Iterator는 자바에서 리스트나 컬렉션의 요소를 순차적으로 탐색하기 위한 객체이다.
LinkedList에서는 아래 두가지 타입의 Iterator를 사용할 수 있다.

• Iterator: 순방향 탐색만 가능한 기본적인 Iterator이다.
• ListIterator: 순방향, 역방향 모두 탐색이 가능한 양방향 Iterator이다.

		// 선언 및 초기화
		ListIterator<ObjectType> iter = list.listIterator();   // 이 형식으로 선언 및 초기화가 가능하다. 
        ListIterator<ObjectType> iter = list.listIterator(list.size());	// 해당 문제에서는 초기에 커서가 가장 우측에 위치하기 때문에 list의 사이즈에 해당하는 iterator를 초기화 해주었다.
        
        //	커서의 다음 혹은 전 위치에 노드가 존재하는지 확인한다. 
        iter.hasPrevious());
        iter.hasNext())
        
        //	커서의 이전 혹은 다음 노드의 요소를 반환한다. 
        iter.previous();
        iter.next();
        
        //	마지막으로 반환된 객체를 제거한다. 반드시 iter.next() 혹은 iter.previous()가 선행호출되어야한다. 
        iter.remove();
        
        // 현재 커서의 위치에 요소를 추가한다.
        iter.add(Element);

세번째 풀이 - Stack 사용

stack은 탐색을 제외한 모든 연산이 O(1)의 시간복잡도를 가진다.
두 개의 stack을 사용한다. 왼쪽에 하나의 스택이 있고, 오른쪽에 또 다른 스택이 존재한다고 생각하자.
왼쪽의 스택에 초기의 문자열을 하나씩 push해준다. 그리고 커서를 왼쪽으로 이동하는 것은 왼쪽 스택에서 pop()한 요소를 오른쪽 스택에 push한다고 생각하고, 커서를 오른쪽으로 이동하는 것은 오른쪽 스택에서 pop한 요소를 왼쪽의 스택에 push한다고 생각하면 된다.
그리고 마지막에 왼쪽에 요소가 남아있다면 모든 요소를 pop한 후 오른쪽에 push하고 오른쪽 스택의 요소들을 pop하면서 출력해주면된다.

package BOJ;

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

public class sol1406_stack {
    static String init;
    static int M;

    static Stack<Character> left;
    static Stack<Character> right;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        init = br.readLine();
        left = new Stack<>();
        right = new Stack<>();
        for (int i = 0; i < init.length(); i++) {
            left.push(init.charAt(i));
        }
        M = Integer.parseInt(br.readLine());
        for (int i = 0; i < M; i++) {
            String command = br.readLine();
            char c = command.charAt(0);
            switch (c) {
                case 'L':
                    if (!left.isEmpty()) right.push(left.pop());
                    break;
                case 'D':
                    if (!right.isEmpty()) left.push(right.pop());
                    break;
                case 'B':
                    if (!left.isEmpty()) left.pop();
                    break;
                case 'P':
                    char add = command.charAt(2);
                   left.push(add);
                    break;

                default:
                    break;
            }
        }
       while(!left.isEmpty()) {
            right.push(left.pop());
        }
        while(!right.isEmpty()) {
            bw.write(right.pop());
        }
        bw.flush();
        bw.close();
    }
}