[백준] 1406번 : 에디터

---

풀이 과정

이 문제는 짧은 시간제한으로 모든 연산이 O(1)의 시간 복잡도를 가지게 구현해야 한다.

1. LinkedList를 사용해서 구현

LinkedList를 선택한 이유는 체인처럼 관리하기 때문에 삽입/삭제에 유리하기에 이번 문제에서 사용하기 적합하다고 생각했다.
하지만, 이 문제는 0.3초의 시간제한으로 더 빠른 처리를 해야한다.
LinkedList는 인덱스를 접근하는 것이 아니라, 최악의 경우 모든 요소를 다 살펴봐야 하기에 적합하지 않았다.

즉 O(N)의 시간 복잡도를 가지게 되어서 시간초과 문제가 났다.

나는 index를 static 변수로 설정해서 L/D/B/P 마다 인덱스를 새로 설정해주는 방식으로 구현했는데, 이 방법은 해당하는 인덱스를 하나하나 찾아서 해당하는 인덱스에 삽입/삭제를 해야하기에 시간초과가 나버렸다.

해결 방법

Stack을 이용해서 해결했다.
Stack은 모든 연산이 O(1)의 시간 복잡도를 가지기 때문에 시간 초과에 걸리지 않는다!

해결 방법은 2개의 Stack을 이용해 해결했다.

구체적인 동작 방식은 코드의 주석을 참고하면 쉽게 이해할 수 있을 것이다.

추가 해결 방법

LinkedList만 사용해서 해결하기엔 검색에 효율이 너무 안나와서 여러 블로그를 참고했다.
해결 방법은 ListIterator를 사용하는 방법이였다.

기존 Iterator와 달리 양방향 탐색이 가능하기 때문에 해당 문제에 매우 적합했다.

코드 참조

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());

		LinkedList<Character> list = new LinkedList<Character>();

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

		//iterator 메소드 호출 
		ListIterator<Character> iter = list.listIterator();
		//처음 커서는 문장의 맨 뒤에 있어야하기 때문에 커서를 맨뒤로 이동시켜줌 (ex. abc|)
		while(iter.hasNext()) {
			iter.next();
		}
	
		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':
				//remove()는 next()나 previous()에 의해 반환된 가장 마지막 요소를 리스트에서 제거함
				if(iter.hasPrevious()) {
					iter.previous();
					iter.remove();
				}
				break;
			case 'P':
				char t = command.charAt(2);
				iter.add(t);

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

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
    static Stack<Character> lStack = new Stack<>();
    static Stack<Character> rStack = new Stack<>();

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


        String str = br.readLine();
        for(int i=0;i<str.length();i++) {
            lStack.add(str.charAt(i));
        }

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

        for(int i=0;i<m;i++) {
            String command = br.readLine();
            switch (command.charAt(0)) {
                case 'L' : CursorL(); break;
                case 'D' : CursorD(); break;
                case 'B' : CursorB(); break;
                case 'P' : {
                    CursorP(command.charAt(2));
                    break;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        while(!rStack.isEmpty()){
            sb.append(rStack.pop());
        }
        sb.reverse();
        while(!lStack.isEmpty()){
            sb.append(lStack.pop());
        }
        System.out.println(sb.reverse());
    }

	// 추가
    private static void CursorP(char s) {
        lStack.push(s);
    }

	// 제거
    private static void CursorB() {
        if(lStack.isEmpty())
            return;
        lStack.pop();
    }

	// 커서 오른쪽 이동 -> r스택에 저장한 값을 가져옴.
    private static void CursorD() {
        if(rStack.isEmpty())
            return;
        char temp = rStack.pop();
        lStack.push(temp);
    }

	// 커서 왼쪽 이동 -> r스택에 값을 저장
    private static void CursorL() {
        if(lStack.isEmpty())
            return;
        char temp = lStack.pop();
        rStack.push(temp);
    }
}