[백준 1406] 에디터 - 자바

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

1406번: 에디터

---

1. 풀이

알고리즘 문제를 푸는데 어떠한 알고리즘을 사용할지 결정하는 것이 매우 중요하다고 느낀 문제이다.
스택에 대해서 잘 안다고 생각했지만, 여전히 응용방면에 있어서는 부족한 듯 싶다.

문제를 처음 봤을때, 문자열을 통한 방법과 연결리스트 사용해서 생각해보았다. 커서의 위치는 정수로 된 위치값으로 해보았다.

 

입력값 : abcdef| 

L : abcde|f 

D : abcdef|

B : abcde|

P f : abcdef|

 

여기서 문제는, B(삭제)와 P(입력)연산이다.

만약 ab|cd 상황에서 B연산을 하면 b가 사라지고, c와 d를 한칸씩 앞으로 미뤄야 한다.

그러므로 O(n)만큼의 시간 복잡도가 나오며, P연산 또한 마찬가지다.

명령의 개수를 곱해주면 O(m*n)의 시간 복잡도가 나오게 된다.

배열의 중간에 추가하는데 걸리는 시간은 배열의 크기와 같다. (하나씩 미뤄야하기 때문에, 너무 오래 걸림)
스택을 사용하면 빠르게 풀이가 가능하다.
스택은 마지막의 요소만 의미를 갖는다. 마지막의 요소에만 의미를 가져야하는 문제에서 스택을 고민해봐도 될 것 같다.

백준 강의를 통해 해결방법을 찾게 되었다. ( 역시 돈을 투자하면 좋은 리턴이 오는것 같다.. )

 

해결 방법은 두 개의 스택 ( Left, Right )을 만들어 커서의 왼쪽에 있는 문자는 Left에, 오른쪽에 있는 문자는 Right에 넣는 것이다.

이렇게 하면 각 명령어당 O(1)만큼의 시간복잡도밖에 걸리지 않게 된다.

 

---

2. 코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();
		Stack<Character> left = new Stack<Character>();
		Stack<Character> right = new Stack<Character>();
		
		// 처음에 커서의 위치는 가장 오른쪽이므로 left에 다 넣어준다.
		for(char ch : input.toCharArray()) {
			left.push(ch);
		}
		
		int num = Integer.parseInt(br.readLine()); // 명령어의 개수
		
		while(num-- > 0) {
			String[] command = br.readLine().split(" ");
			// 커서를 왼쪽으로 -> left의 top문자를 right으로 push
			if(command[0].equals("L")) {
				if(!left.isEmpty())
					right.push(left.pop());
			} 
			// 커서를 오른쪽으로 -> right의 top문자를 left에 push
			else if(command[0].equals("D")) {
				if(!right.isEmpty())
					left.push(right.pop());
			} 
			// 커서의 왼쪽 삭제 -> left의 top문자 pop
			else if(command[0].equals("B")) {
				if(!left.isEmpty())
					left.pop();
			} 
			// 커서의 왼쪽에 새로운 문자 입력 -> left에 새로운 문자 push
			else if(command[0].equals("P")) {
				left.push(command[1].charAt(0));
			}
		}
		
		// 출력을 위해서 left stack의 문자를 모두 right으로 옮기기
		while(!left.isEmpty()) {
			right.push(left.pop());
		}
		
		// 출력
		while(!right.isEmpty()) {
			System.out.print(right.pop());
		}
		
		return;
	}
}