백준 1406 <에디터>

1406번: 에디터 (acmicpc.net)

1406번: 에디터

명령어 4가지를 통해 문자열을 control해보는 문제. 커서를 활용하는 특이한 문제다.

특이한 점은 시간제한이 빡세다 0.3초.. 

 

첫번째 접근.

그냥 stringBuilder와 인덱싱 활용해서 풀기, - 답은 맞게나오나, 성능이 o(n)으로 낫배드나, 0.3초라 시간제한에 걸렸다

 

두번째 접근

커서 활용 >> LinkedList의 ListIterator로 문제 해결하기. 얘는 시간제한에 안걸리고 풀었다

iterator의 next, hasnext, previous, hasprevious로 커서를 control하는 것.

또한 add()메서드 remove()메서드,  다 있으니 문제에서 요구하는 것을 쉽게 처리할 수가 있다;

switch - case문 만들어서 했는데 시간 더 줄여보려고,, 근데 한참 어지러웠던게 switch-case문에서 순서가 엄청 중요했다는 것이다. 난 그냥 랜덤으로 하나씩 case에다가 넣었는데 그러면 안됐다. 문제에서 주어진 L,D,B,P 순서로 구현하니 답이 맞았다. switch case문은 조건문과는 사뭇 다른갑다.

package 배열;
import java.io.*;
import java.util.*;

public class _1406_에디터_using_ListIterator {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		String str = br.readLine();
		int M = Integer.parseInt(br.readLine());

		LinkedList<Character> list = new LinkedList<Character>();

		for(int i = 0; i < str.length(); i++) {
			list.add(str.charAt(i));
		}

		//iterator 메소드 호출 
		//iter은 커서의 역할.
		ListIterator<Character> iter = list.listIterator();
		//처음 커서는 문장의 맨 뒤에 있어야하기 때문에 커서를 맨뒤로 이동시켜줌 (ex. abc|)
		while(iter.hasNext()) {
			iter.next();
		}
			
		for(int i = 0; i < M; i++) {
			String command = br.readLine();
			char c = command.charAt(0);
			switch(c) {
			case 'L':
				if(iter.hasPrevious())
					iter.previous();

				break;
			case 'D':
				if(iter.hasNext())
					iter.next();

				break;
			case 'B':
				//remove()는 next()나 previous()에 의해 반환된 가장 마지막 요소를 리스트에서 제거함
				if(iter.hasPrevious()) {
					iter.previous();
					iter.remove();
				}
				break;
			case 'P':
				char t = command.charAt(2);
				iter.add(t);

				break;
			
			}
		}
		for(Character chr : list) {
			sb.append(chr);
		}
		
		System.out.println(sb);
	}
}

 

세 번째 접근. 스택 활용하기 

요건 참신했다. 구글링 해서 코드를 참고했는데 아이디어는 간단하다. 스택 2개를 활용하여 PUSH POP을 두번 반복하면 문자열 그대로 OUTPUT이 가능하니 이를 이용한것.

 

1.주어지는 문자열을 왼쪽스택에다 넣는다. (이러면 STACK의 LIFO구조로 반대로 쌓인다.

 

2. (명령어 P) 

이때, 새로운 문자가 들어오면 왼쪽에 넣어준다.

 

3.(명령어 L)

커서를 왼쪽으로 옮긴다. 옮기는 순간, 커서 기준 오른쪽 문자는 건들여지지 않겠다. 따라서 커서 왼쪽에 있었던 문자는 오른쪽 스택으로 옮겨둔다.

 

4.(명령어 D)

커서를 오른쪽. 이렇게 되면 오른쪽에 있던 문자 하나는 건들여지겠다. 따라서 오른쪽에서 왼쪽으로 옮겨준다

 

5.(명령어 B)

커서 왼쪽 문자하나 삭제. 왼쪽 스택하나 POP시켜준다.

 

이렇게 하고난 후 왼쪽에 있던 스택을 RIGHT에다가 POP해주고, RIGHT을 다시 POP해준다면 우리가 원하는 조정된 정방향의 문자열이 정상적으로 출력된다.

이 방법이 좋았던 건 스택의 메서드는 O(1)이라 상당히 시간 효율적.. 이 방법 알고가자.

package 스택과큐;
import java.io.*;
import java.util.*;

public class _1406_에디터_using_Stack {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		Stack<String> left = new Stack<>();
		Stack<String> right = new Stack<>();
		String str = br.readLine();
		String[] arr = str.split("");
		for(String st : arr) {
			left.push(st);
		}
		
		int n = Integer.parseInt(br.readLine());
		for(int i=0; i<n; i++) {
			String test = br.readLine();
			char c = test.charAt(0);
			switch(c) {
			case 'L':
				if(!left.isEmpty())
					right.push(left.pop());

				break;
			case 'D':
				if(!right.isEmpty())
					left.push(right.pop());

				break;
			case 'B':
				if(!left.isEmpty()) {
					left.pop();
				}
				break;
			case 'P':
				char t = test.charAt(2);
				left.push(String.valueOf(t));
				//leftSt.push(st.nextToken());

				break;
			default:
				break;
				
		}
		}
		
		while(!left.isEmpty()) {
			right.push(left.pop());
		}
		while(!right.isEmpty()) {
			bw.write(right.pop());
		}
		bw.flush();	

}
}