[백준 Java] 1406번 에디터 (스택)

 

[Silver II] 에디터 - 1406

문제 링크

성능 요약

메모리: 85980 KB, 시간: 468 ms

분류

자료 구조, 연결 리스트, 스택

문제 설명

한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.

이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.

이 편집기가 지원하는 명령어는 다음과 같다.

L	커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)
D	커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)
B	커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨) 삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임
P $	$라는 문자를 커서 왼쪽에 추가함

초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.

입력

첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 M(1 ≤ M ≤ 500,000)이 주어진다. 셋째 줄부터 M개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다. 명령어는 위의 네 가지 중 하나의 형태로만 주어진다.

출력

첫째 줄에 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 출력한다.

💡 나의 접근

처음에는 간단하게 ArrayList를 이용해서 접근했다가 시간초과가 나고 LinkedList로 접근했다가 시간초과가 나서 어떻게 하나 하다가 스택을 사용해야한다는 것을 알게 됐다.

 

ArrayList는 배열의 형태로 데이터가 저장되어 있어 인덱스로 접근이 가능해 참조하는데에는 O(1)의 시간이 걸리나 

데이터를 삽입 또는 삭제하는 과정에서 데이터를 밀고 당기는 과정이 있기 때문에 O(n)만큼의 시간이 걸린다.

 

LinkedList는 다음 노드의 위치를 저장하고 있는 header가 있기 때문에 삽입, 삭제 하는 과정에서 가르키는 노드만 바꿔주기만 하면되서 O(1) 만큼의 시간이 걸리나 삽입할 위치, 삭제할 데이터를 찾아가는 과정에 노드를 타고타고 가야하기때문에 O(n)만큼의 시가니 걸리게 된다.

 

그래서 삽입, 삭제가 O(1)만큼의 시간이 걸리는 자료구조는 stack!!

Stack은 후입선출이며 나중에 쌓인게 가장 먼저 나간다.

stacak의 push(), pop()의 시간복잡도는 O(1)이며

contains()와 같은 탐색 함수는 O(n)이다.

 

 

문제 접근 방법은 간단하다.

주어진 각 명령어 대로 구현하면 되는데

이때 커서를 기준으로 왼쪽에 존재하는 문자들을 담을 스택과

오른쪽에 존재하는 문자들을 담을 스택, 총 2개를 만들어 주면 된다.

이때 주의해야하는 것은 오른쪽 스택에는 d, e 순서가 아닌 e d 순서로 들어가게 된다는 것이다.

 

처음에 입력을 받을때는 커서가 항상 제일 오른쪽에 위치하게 되므로 왼쪽스택에 모두 담으면 된다.

마지막 출력할때는 왼쪽에서 하나씩 빼서 오른쪽으러 넣은 후 다시 빼서 StringBuilder에 append 해주었다.

 

명령어 L은 커서를 왼쪽으로 한칸 옮기게 되므로 커서 기준 오른쪽 스택에 문자가 옮겨가게 된다.

D는 반대이다.

B는 왼쪽 스택에 존재하는 최상단 문자열을 제거한다.

P $는 커서의 왼쪽에 문자를 추가하며 되므로 왼쪽 스택에 문자를 삽입한다. 

 

아래의 그림은 문제 예제 입력 1을 그림으로 표현한 것이다.

 

1. 주어진 input을 입력 후 상태

2. P x 실행

3. L 실행

 

4. P y

.

이 상태가 최종 상태로 되고 L 스택에서 R로 옮기게 되면 R 스택은

a

b

c

d

y

x

순서대로 쌓이게 된다. 

이를 위에부터 차근히 뽑아 출력하면 된다.

 

💡 코드

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

public class Main {
	/* 스택을 활용
	 * 스택의 삽입, 삭제, 읽기 모드 O(1)
	 * 탐색은 O(n)
	 * 
	 * 커서 기준 왼쪽 스택과 오른쪽 스택을 나누어 구현
	 */
	static Stack<Character> leftStr;
	static Stack<Character> rightStr;
	static int N;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();

		leftStr = new Stack<>();
		rightStr = new Stack<>();
		for (int i = 0; i < str.length(); i++) {
			leftStr.push(str.charAt(i));
		}

		N = Integer.parseInt(br.readLine());

		for (int i = 0; i < N; i++) {

			String op = br.readLine();

			switch (op.charAt(0)){
				case 'L': {
					if(!leftStr.isEmpty()) {
						rightStr.push(leftStr.pop());
					}
					break;
				}

				case 'D': {
					if(!rightStr.isEmpty()) {
						leftStr.push(rightStr.pop());
					}
					break;
				}

				case 'B': {
					if(!leftStr.isEmpty()) {
						leftStr.pop();
					}
					break;
				}

				case 'P': {
					char c = op.charAt(2);
					leftStr.push(c);
					break;
				}
			}
		}


		while (!leftStr.isEmpty()) {
			rightStr.push(leftStr.pop());
		}

		StringBuilder sb = new StringBuilder();
		while (!rightStr.isEmpty()) {
			sb.append(rightStr.pop());
		}

		System.out.println(sb.toString());
	}
}