백준1406_에디터 (java)

https://www.acmicpc.net/problem/1406

1406번: 에디터

문제 풀이 방식

1. 나의 생각
   • LinkedList를 이용
   • 이유는 커서가 앞과 뒤 뿐만 아니라 중간에 문자와 문자사이에도 들어가 값을 추가하거나 삭제할 수 있어야하기 때문이다.
   • 그래서 LinkedList에 입력받은 문자열을 저장
   • 제일 마지막 인덱스를 커서의 인덱스로 설정해준 후, swicth-case문을 이용해 각 명령어에 따라서 커서의 인덱스를 옮겨주거나 값을 삭제 또는 추가하여야겠다고 생각했다. 즉, 삽입과 삭제가 용이해야한다고 생각했기에 해당 자료구조를 선택하였다.
2. 찾아본 풀이법
   • 블로그를 서칭해보니 문제의 조건 때문에 O(M)복잡도로 풀어야한다고 한다. 제한시간이 0.3초이고 60만글자까지 입력할 수 있기때문에, 최악의 경우 인덱스를 탐색하는데 N만큼 걸릴 수 있다.
   • 따라서 Listiterator나 스택을 사용하면 제한시간내에 풀 수 있다고 한다.
   • 스택을 사용하는 방법은 키로거 문제와 비슷하다.

그래서 Listiterator를 사용해 풀어볼 것이다.

 

수도코드로 나타내보았다.

 

String str = input();
int n = input();

LinkedList<Character> list = new LinkedList<>();
for(int i=0; i<str.length(); i++) list.add(str.charAt(i)); // 문자열을 list에 담음

// ListIterator<Character> cursor = list.listIterator(); // listIterator메소드 호출

// while(cursor가 값을 가지고 있는동안)
//		cursor.next(); // 처음에는 cursor의 위치를 제일 마지막에 놔둬야함.

// 위의 방법을 이렇게 바꿈 list.size()하면 맨 마지막에 커서를 놔둘 수 있다.
ListIterator<Character> cursor = list.listIterator(list.size());

for(int i=0; i<M; i++) { // 명령어를 M번만큼 반복
	String[] tmp = input().split(" ");
	char 명령어 = tmp[0];

	switch(명령어) {
		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(); // remove()는 next(), previous()에 의해 반환된 가장 마지막 요소를 삭제
				break;
		case 'P':
			char c = tmp[1];
			cursor.add(c);
			break;
		default:
			break;	
	}
}
for(char x : list) 
	sb.append(x).append(" ");

print(sb);