[백준 1406번] 에디터 (java)

백준 1406번 : 에디터

1406번: 에디터

 

스택을 이용하여 문제를 풀었다.

 

 

[1차 시도]

처음에는 stack을 하나 만들어서 문자열의 문자들을 스택에 넣고, cursor 변수를 만들어서 명령어에 따라 커서의 위치를 갱신시켰다.

명령어 B(커서 전 문자 삭제)가 나오면, 

현재 스택에 들어있는 문자의 개수 - cursor 만큼 스택에서 문자들을 pop을 한 다음에(그러면 스택의 맨 위에는 현재 커서 위치 바로 직전의 문자가 남아있게 된다.) 이 문자들을 임시 스택 tmp에 넣고,

제거되어야 할 문자를 제거한 후, 다시 tmp -> stack 으로 문자열을 옮겨 담았다.

 

명령어 P(커서 뒤에 문자 추가)가 나오면,

현재 스택에 들어있는 문자의 개수 - cursor 만큼 스택에서 문자들을 pop을 한 다음에(그러면 스택의 맨 위에는 현재 커서 위치 바로 직전의 문자가 남아있게 된다.) 이 문자들을 임시 스택 tmp에 넣고, stack에 추가할 문자를 push 한 뒤,

tmp -> stack 으로 문자열을 옮겨 담았다.

 

소스 코드 :

import java.io.*;
import java.util.*;

public class Main {

	static String str;
	static int N, M;

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		str = br.readLine();
		N = str.length();
		M = Integer.parseInt(br.readLine());

		Stack<Character> stack = new Stack<>();
		for (int i = 0; i < N; i++)
			stack.push(str.charAt(i));

		int cursor = N;

		for (int i = 0; i < M; i++) {
			String[] sarr = br.readLine().split(" ");
			String cmd = sarr[0];

			switch (cmd) {
			case "L":
				cursor = Math.max(0, cursor - 1);
				break;
			case "D":
				cursor = Math.min(N, cursor + 1);
				break;
			case "B":
				if (cursor > 0) {
					int d = stack.size() - cursor;
					Stack<Character> tmp = new Stack<>();
					while (d > 0) {
						tmp.push(stack.pop());
						d--;
					}
					stack.pop();
					while (!tmp.isEmpty())
						stack.push(tmp.pop());

					cursor--;
				}
				break;
			case "P":
				char ch = sarr[1].charAt(0);

				int d = stack.size() - cursor;
				Stack<Character> tmp = new Stack<>();
				while (d > 0) {
					tmp.push(stack.pop());
					d--;
				}
				stack.push(ch);
				while (!tmp.isEmpty())
					stack.push(tmp.pop());

				cursor++;
				break;
			}
		}

		StringBuffer buf = new StringBuffer();
		while (!stack.isEmpty())
			buf.append(stack.pop());

		String res = buf.reverse().toString();

		bw.write(res + "\n");
		bw.flush();

	}

}

그런데 결과는 시간 초과

위 코드는 커서의 위치 오른쪽에 있는 문자들을 stack에서 pop한 후 tmp로 옮겨담고,

명령어 처리를 한 뒤(삭제 OR 추가), 다시 tmp에서 stack으로 문자들을 옮기는 과정에서 시간이 많이 소모된다.

 

 

그래서 다른 블로그를 참고하여 아이디어를 얻었다.

 

cursor를 이동하는 것이 아니라, 애초에 스택을 두 개 만들어서 

Stack<Character> left = new Stack<>();

Stack<Character> right = new Stack<>();

"커서의 왼쪽에 있는 문자들과 커서의 오른쪽에 있는 문자들을 각각 다른 스택에 담는다."

그러면 각 명령어마다 left 혹은 right 스택에 push, pop만 하면 되기 때문에 전 코드에 비해 훨씬 시간이 줄어 들게 된다.

 

소스코드 :