백준 1406 (에디터)

문제

---

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

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

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

 

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

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

 

풀이

---

list 를 이용해서 풀었다. list 를 이용해서 푸는 방식은 직관적으로 방식 자체는 간단했지만 string을 char 형으로 변환후 넣는 과정이 오래걸리나 보다. 시간초과가 떴다.

 

<시간초과 코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

public class Main {	
	
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//Scanner scanner = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		
		String line = br.readLine();
		
		List<Character> list = line.chars().mapToObj(e -> (char) e).collect(Collectors.toList());
		int index = 0;		
			
		index = list.size();
		
		int n = Integer.parseInt(br.readLine());
		
		for(int i = 0 ; i < n ; i++) {
			line = br.readLine();
			String[] doing = line.split("\\s");
			
			switch(doing[0]) {
			
			case "L":
				if(index > 0)
					index--;
				break;
			case "D":
				if(index < list.size())
					index++;
				break;
			case "B":
				if(index > 0) {
					list.remove(index-1);
					index--;	
				}
				break;
			case "P":
				list.add(index, doing[1].charAt(0));
				index++;
				break;
			}
		}
		
		/*
		 * for(char tmp : list) { sb.append(tmp); }
		 */
		sb.append(list.toString());
		System.out.println(sb);
	}
	
}

 

인터넷에 Stack 을 이용 한 풀이가 있다고 보고 풀었다.

Stack 을 두개 만들어서 LeftStack 과 RightStack 으로 해서 풀수 있다. LeftStack 의 끝이 커서의 위치로 지정을하고 문제를 푸는 방식으로 풀었다.

 

JAVA 11 을 이용하다 보니 알고리즘의 문제가아닌 출력과 입력에서의 시간이 너무 많이 사용되는 단점이 있어서 시간초과가 많이 뜬다.

이부분을 여기서는 Stack.foreach 를 통해 시간복잡도를 최소한으로 하였다.

 

<코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.stream.Collectors;

public class Main {	
	
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//Scanner scanner = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		
		String line = br.readLine();
		Stack<Character> left_Stack = new Stack<Character>();
		Stack<Character> right_Stack = new Stack<Character>();
		
		for(int i = 0 ; i < line.length() ; i++) {
			left_Stack.push(line.charAt(i));
		}
	
		
		int n = Integer.parseInt(br.readLine());
		
		for(int i = 0 ; i < n ; i++) {
			line = br.readLine();		
			
			if(line.contains("L")) {
				if(!left_Stack.empty()) {
					right_Stack.push(left_Stack.pop());
				}
			}
			else if(line.contains("D")) {
				if(!right_Stack.empty()) {
					left_Stack.push(right_Stack.pop());
				}

			}
			else if(line.contains("B")) {
				if(!left_Stack.empty()) {
					left_Stack.pop();
				}
			}
			else if(line.contains("P")) {
				left_Stack.push(line.charAt(2));
				
			}
		}
		
		left_Stack.forEach(item->sb.append(item));
		
		while(!right_Stack.empty()) {
			sb.append(right_Stack.pop());			
		}
		
		System.out.println(sb);
	}
	
}