[백준] 1406. 에디터

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

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

		ArrayList<Character> char_arr = new ArrayList<>();

		for (char c : br.readLine().toCharArray()) {
			char_arr.add(c);
		}
		StringTokenizer st;
		int cursor = char_arr.size();
		int N = Integer.parseInt(br.readLine());
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");

			switch (st.nextToken().charAt(0)) {
			case 'L':
				if (cursor > 0)
					cursor--;
				break;
			case 'D':
				if (cursor < char_arr.size() - 1)
					cursor++;
				break;
			case 'B':
				if (cursor > 0) {
					char_arr.remove(cursor - 1);
					cursor--;
				}
				break;
			case 'P':
				char_arr.add(cursor, st.nextToken().charAt(0));
				cursor++;
				break;
			}
		}

		for (char c : char_arr) {
			bw.write(c + "");
		}

		bw.flush();
		br.close();
		bw.close();
	}
}

이렇게 작성하였더니 시간초과가 났다.

먼저, LinkedList대신 ArrayList를 사용하여서 k 번째 원소의 접근은 O(k)이지만, 삽입, 삭제 연산이 O(N)이다.

 

또, ArrayList 대신 LinkedList를 사용했다고 하여도 연결리스트에서 임의의 위치에 원소의 추가/삭제는 O(1)이지만 이 경우는 추가/삭제 하고 싶은 위치의 주소를 알고 있는 경우에만 O(1)이다. 임의의 위치의 주소를 모른다면 k번째 원소에 접근하기 위하여 O(k)가 걸린다.

 

하단은 문제의 커서의 역할을 하는 ListIterator를 활용한 코드이다.

ListIterator를 활용하면 cursor의 위치가 추가한 요소에 존재한다.

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

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

		LinkedList<Character> list = new LinkedList<>();
		ListIterator<Character> iter = list.listIterator();

		for (char c : br.readLine().toCharArray()) {
			iter.add(c);
		}

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

		while (N-- > 0) {
			char[] input = br.readLine().toCharArray();

			switch (input[0]) {
			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;
			default:
				iter.add(input[2]);
				break;
			}
		}

		for (char c : list) {
			bw.write(c + "");
		}

		bw.flush();
		br.close();
		bw.close();
	}
}