[백준_1406번] 에디터

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

1406번: 에디터

[문제]

한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다. 이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다. 이 편집기가 지원하는 명령어는 다음과 같다.

 

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

 

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

 

[입력 조건]

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

 

[코드]

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

public class BaekJoon_1406 {
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		
		String str=br.readLine();
		int n=Integer.parseInt(br.readLine());
		
		/*
		 * leftStack에는 입력받은 문자열의 문자들이 아래부터 저장되어 있고
		 * 커서의 초기 위치는 문자열의 제일 위에 있기 때문에 leftStack의 제일 위의 문자 뒤에 위치한다.
		 * 
		 * leftStack에는 커서를 기준으로 왼쪽에 위치한 문자들이 아래부터 저장되어 있고,
		 * rightStack에는 커서를 기준으로 오른쪽에 위치한 문자들이 아래부터 저장되어 있다.
		 */
		Stack<Character> leftStack=new Stack<>();
		Stack<Character> rightStack=new Stack<>();
		
		for(int i=0;i<str.length();i++)
			leftStack.push(str.charAt(i));
		
		while(n-->0) {
			String command=br.readLine();
			char c=command.charAt(0);
			
			switch(c) {
			/*
			 * 커서를 한칸 왼쪽으로 옮길 경우에는 커서를 오른쪽으로 한칸 옮겼을 때
			 * rightStack으로 이동한 문자를 다시 leftStack으로 옮겨온다.  
			 */
			case 'L':
				if(!leftStack.isEmpty())
					rightStack.push(leftStack.pop());
				break;
			/*
			 * 커서를 한칸 오른쪽으로 옮길 경우에는 커서가 이동한것 처럼 보이기 위해
			 * leftStack의 제일 위에있는 값을 rightStack으로 이동시킨다.  
			 */	
			case 'D':
				if(!rightStack.isEmpty())
					leftStack.push(rightStack.pop());
				break;	
			/*
			 * 커서의 왼쪽에 있는 문자를 제거하는 경우이기 때문에 
			 * leftStack의 제일 위에있는 값을 삭제해준다.
			 */
			case 'B':
				if(!leftStack.isEmpty())
					leftStack.pop();
				break;	
			/*
			 * 입력받은 문자를 커서 왼쪽에 삽입하는 경우이기 때문에 
			 * 커서는 항상 leftStack의 제일 위에있는 문자 다음에 위치해있으므로
			 * leftStack의 제일 위에 문자를 삽입한다. 
			 */
			case 'P':
				char ch=command.charAt(2);
				leftStack.push(ch);
				break;	
			default:
				break;
			}
		}
		
		/*
		 * 스택은 LIFO 구조이기 때문에 
		 * leftStack에 있는 값들을 아래서부터 출력하기 위해서는
		 * rightStack에 저장한 후 rightStack 값을 위에서부터 꺼내 출력한다. 
		 */
		while(!leftStack.isEmpty())
			rightStack.push(leftStack.pop());
		
		while(!rightStack.isEmpty())
			bw.write(rightStack.pop());
		
		bw.flush();
		bw.close();
	}

}

 

[고찰]

 처음에는 해당 문제를 연결리스트와 Scanner를 사용하여 접근하여 했으나, 연결리스트를 사용할 경우 중간에 문자를 삭제, 삽입하는 경우 삽입된 위치로부터 이후의 인덱스를 변경해야하는 문제가 생겨 시간초과를 받을 수 밖에 없었다. 시간초과 없이 문제를 해결할 방법이 떠오르지 않아 다른 사람들의 코드를 참고하니 스택이라는 자료구조를 사용하면 인덱스 이동 없이 문제를 해결할 수 있다는 것을 배웠다. 

 위의 문제를 해결하기 위한 스택은 총 2개를 선언해야 한다. 커서를 기점으로 왼쪽에 있는 문자를 저장하는 leftStack, 오른쪽에 있는 문자를 저장하는 rightStack이 그것이다. 이렇게 두 개의 스택을 선언하면 커서가 실제 이동하는 것 처럼 문제를 풀 수 있다. 

 스택이란 자료구조는 자료구조를 배울 당시 거의 초반에 배우는 자료구조로 비교적 친숙하지만 아직 문제에 적용하여 해결하는 능력은 미숙한 것 같다. 좀 더 노력이 필요하다고 느꼈다.