백준 1406번) 에디터(ListIterator)

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

public class Main {
	static ArrayList<String> list ;
	static ArrayList<String> command ;
	static int cursor;

	static void backCursor() {
		if(cursor==0)
			return;
		cursor--;

	}
	static void forwardCursor() {
		if(cursor>=list.size())
			return;
		cursor++;
	}
	static void delete() {
		if(cursor==0)
			return;
		list.remove(--cursor);
	}
	static void addChar(String string) {
		list.add(cursor, string);
		cursor++;

	}

	static void doCommand() {
		for(int i=0; i<command.size();i++)
		{
			if(command.get(i).equals("L"))
				backCursor();
			if(command.get(i).equals("D"))
				forwardCursor();
			if(command.get(i).equals("B"))
				delete();
			if(command.get(i).split(" ")[0].equals("P"))
				addChar(command.get(i).split(" ")[1]);
		}

	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		String str = reader.readLine();
		int N = Integer.parseInt(reader.readLine());
		list =  new ArrayList<String>();
		command =  new ArrayList<String>();
		cursor = str.length();
		for (int i = 0; i <N; ++i)
		{
			command.add(reader.readLine());
		}
		for (int i = 0; i <str.length(); ++i)
			list.add(Character.toString(str.charAt(i)));
		doCommand();
		System.out.println(list.toString().replace("[","").replace("]","").replace(", ", ""));



	}

}

시간초과 나옴.....ㅠㅠ흐규흐규
LinkedList를 사용한다고 해도 찾아가서 처리하기때문에 O(n)의 시간 복잡도를 가지게 되어 그런거 같다. 더 짧은 시간복잡도가 필요한 문제

교수님 자료의 도움으로
ListIterator를 사용한다면 좀 더 효율적인것을 알게되었다.

-----------------수정------------------

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

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		String s = reader.readLine();
		LinkedList<Character> list = new LinkedList<>();
		for (char c : s.toCharArray())
			list.add(c);
		int N = Integer.parseInt(reader.readLine());
		ListIterator<Character> iterator = list.listIterator(list.size());
		for (int i = 0; i < N; ++i) {
			StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
			String cmd = tokenizer.nextToken();
			switch (cmd) {
			case "L":
				if (iterator.hasPrevious())
					iterator.previous();
				break;
			case "D":
				if (iterator.hasNext()) //
					iterator.next();
				break;
			case "B":
				if (iterator.hasPrevious()) {
					iterator.previous();
					iterator.remove();
				}
				break;
			case "P":
				iterator.add(tokenizer.nextToken().charAt(0));
				break;
			}
		}
		StringBuilder builder = new StringBuilder();
		for (char c : list)
			builder.append(c);
		System.out.println(builder.toString());
	}
}

ListIterator

• ArrayList나 LinkedList와 같이 List인터페이스를 구현한 컬렉션에서만 사용
• Iterator는 단방향으로만 이동할 수 있는 데 반해 ListIterator는 양방향으로의 이동이 가능

list.listIterator(list.size());

• list.size()위치에서부터 시작

boolean hasNext()

• Iterator를 앞방향으로 진행하며 객체를 확인
• iteration이 객체(elements)를 더 갖고 있으면 true 그외 false

boolean hasPrevious()

• Iterator가 반대방향으로 진행하며 객체를 확인
• iteration이 객체(elements)를 더 갖고 있으면 true 그외 false

Object next()

• iteration에서 다음 객체를 리턴

Object previous()

• iteration에서 이전 객체를 리턴

void remove()

• next() 또는 previous()로 리턴된 마지막 객체를 제거

void set(Object o)

• next() 또는 previous()로 리턴된 마지막 객체와 o를 바꿉니다.

int nextIndex()

• next() 호출로 리턴될 객체의 인덱스

int previousIndex()

• previous()호출로 리턴될 객체의 인덱스

void add(Object o)

• list에 객체 o를 추가합니다.

검색해보니까 LinkedList보다 Stack을 이용해도 해결 가능하다고 한다.