문제 정리

---

커서를 이용해 명령어를 처리하고 그 결과를 출력하는 문제다.
문제는 간단하지만
문자열의 길이가 10만이 최대, 명령어는 50만개가 최대라는 점이 이 문제의 난이도를 올렸다.
시작시 커서는 문자열의 맨 마지막이다

입력

기존 문자열
명령어 개수
명령어 한 줄에 하나씩

출력

최종 문자열

idea 정리

아직 시간 복잡도를 잘 계산하지 못해서 삽질을 많이 했다.
내가 시도했던 방법들을 정리해보자면

1. List + pointer
List에 문자열을 넣고 integer pointer를 이용해 현재 커서의 위치를 저장한다.
pointer의 위치가 문자 사이냐 아니면 특정 문자를 가리키냐에 따라 구현이 헷갈릴 수 있고
List의 특성상 삽입 삭제에 기존 원소들의 shift 연산이 일어나 overhead가 발생한다.

2. LinkedList + ListIterator
질문글에서 추천받은 ListIterator다. 진짜 커서처럼 특정 위치를 가리키고 previous, next, remove 등등 커서를 기준으로 삽입, 삭제, 이동 연산이 가능하다
1번에서 생긴 shift overhead는 없앨 수 있겠지만 ListIterator의 특성상
처음 초기화시 LinkedList의 첫 번째 원소를 가리키고 있어
문제의 조건인 커서는 문자열의 마지막이다 를 맞춰주려면
커서를 맨 뒤로 옮겨야하는데
여기서 overhead가 발생해서 시간초과가 났다.

3. Stack
커서 기준 왼쪽 문자열, 오른쪽 문자열로 나눠 stack으로 관리해 준다.

그림으로 그려보면 이런 모양이다.
push, pop으로 insert, delete 연산을 실행할 수 있어서 구현도 간단하다.
다만 마지막에 최종 문자열을 만들때 left의 문자열들은 stack에서 빼서 뒤집어 줘야 해서 약간 overhead가 생겼다.

4. deque
stack으로 문제를 풀고 시간이 빠른 코드를 찾아보니 deque로 구현한 코드를 발견했다. 아무래도 stack은 문자열을 뒤집어 줘야하는데 deque는 그런게 필요없으니 시간이 많이 줄어들긴 했다.

구현

---

3번 stack으로 구현하는 방식이다

//에디터
public class Main {
	static Stack<Character> left, right;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		left = new Stack<>();
		right = new Stack<>();
		char[] input = br.readLine().toCharArray();
		for(int i=0,size=input.length; i<size; i++) {
			left.add(input[i]);
		}
		
		int cnt = Integer.parseInt(br.readLine());
		for(int i=0; i<cnt ; i++) {	//명령어 처리
			input = br.readLine().toCharArray();
			switch(input[0]) {
			case 'L': moveLeft(); 			break;
			case 'D': moveRight(); 			break;
			case 'B': deleteLeft();			break;
			case 'P': appendRight(input[2]);break;
			}
		}
		
		StringBuilder leftStr = new StringBuilder();
		while(!left.isEmpty()) {
			leftStr.append(left.pop());
		}
		leftStr.reverse();
		bw.write(leftStr.toString());

		while(!right.isEmpty()) {
			bw.write(right.pop());
		}
		bw.flush();
		bw.close();
		br.close();
	}
	
	static void moveLeft() {
		if(left.isEmpty()) return;
		char c = left.pop();
		right.push(c);
	}
	
	static void moveRight() {
		if(right.isEmpty()) return;
		char c = right.pop();
		left.push(c);
	}
	
	static void deleteLeft() {
		if(left.isEmpty()) return;
		left.pop();
	}
	
	static void appendRight(char c) {
		left.push(c);
	}
}

결과

---