[Java] 백준 1406 - 에디터

문제

---

풀이과정

처음에는 int 변수에 커서의 위치를 기록하고 LinkedList의 add, remove 메소드를 활용하여 풀었지만 시간초과. 결국 직접 구현해서 풀었음.

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

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		char[] initialText = br.readLine().toCharArray();
		int M = Integer.parseInt(br.readLine());
		char[] text = new char[600001];
		int[] pre = new int[600001];
		int[] nxt = new int[600001];
		int cursor = initialText.length;
		int unused = cursor + 1;

		for (int i = 0; i < cursor; i++) {
			text[i] = initialText[i];
			pre[i] = i - 1;
			nxt[i] = i + 1;
		}
		pre[0] = -1;
		pre[cursor] = cursor - 1;
		nxt[cursor] = -1;

		while (M-- > 0) {
			switch (br.read()) {
			case 'L':
				if (pre[cursor] > -1) {
					cursor = pre[cursor];
				}
				break;
			case 'D':
				if (nxt[cursor] > -1) {
					cursor = nxt[cursor];
				}
				break;
			case 'B':
				if (pre[cursor] > -1) {
					if (pre[pre[cursor]] > -1) {
						nxt[pre[pre[cursor]]] = cursor;
					}
					pre[cursor] = pre[pre[cursor]];
				}
				break;
			case 'P':
				br.read();
				text[unused] = (char) br.read();
				pre[unused] = pre[cursor];
				nxt[unused] = cursor;
				if (pre[cursor] > -1) {
					nxt[pre[cursor]] = unused;
				}
				pre[cursor] = unused;
				unused++;
				break;
			default:
				break;
			}
			br.readLine();
		}

		while (pre[cursor] > -1) {
			cursor = pre[cursor];
		}
		
		while (nxt[cursor] > -1) {
			sb.append(text[cursor]);
			cursor = nxt[cursor];
		}

		System.out.println(sb.toString());
		br.close();

	}

}

 

구글링해보니 LinkedList의 add와 remove 메소드는 처음부터 주어진 인덱스까지 탐색하여 접근하기 때문에 O(n)의 시간이 걸림. 이럴때는 ListIterator 활용하면 처음부터 쭉 확인하는 것이 아닌 iterator의 위치에서 삽입 및 삭제 가능. 

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.ListIterator;

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		LinkedList<Character> list = new LinkedList<>();
		char[] initialText = br.readLine().toCharArray();
		int N = initialText.length;
		int M = Integer.parseInt(br.readLine());

		for (int i = 0; i < N; i++) {
			list.add(initialText[i]);
		}

		ListIterator<Character> cursor = list.listIterator(N);

		while (M-- > 0) {
			switch (br.read()) {
			case 'L':
				if (cursor.hasPrevious()) {
					cursor.previous();
				}
				break;
			case 'D':
				if (cursor.hasNext()) {
					cursor.next();
				}
				break;
			case 'B':
				if (cursor.hasPrevious()) {
					cursor.previous();
					cursor.remove();
					N--;
				}
				break;
			case 'P':
				br.read();
				cursor.add((char) br.read());
				N++;
				break;
			default:
				break;
			}
			br.readLine();
		}

		for (char i : list) {
			sb.append(i);
		}
		System.out.println(sb.toString());
		br.close();

	}

}