백준 1406번 에디터 [JAVA]

문제

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

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

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

 

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

입력

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

출력

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

 

 

 

 

 

알고리즘 설계:

일단 문제를 딱 보고 한번에 이해하기 쉽지 않은 문제였다

커서가 바뀔때마다 count값을 증가시켜야되나... 뭐 어떻게 해야되나.. 고민이 많았다 

그래서 결국 아이디어만 얻자는 심정으로 백준 사이트의 강의를 봤다

커서를 기준으로 왼쪽 stack과 오른쪽 stack으로 나눠서 풀면 효율적인 문제였다 

정말 이런생각을 하는게 알고리즘을 잘하는거구나 라는것을 느꼈고

이런 구상만 한다면 그 다음부터 코드 작성하는건 쉬운거라는걸 느꼈다

 

1. 일단 character형으로 왼쪽 stack과 오른쪽 stack을 만든다 

2. 처음 입력한 문자열은 왼쪽 stack에 push한다

 

3. 쉬운 이해를 위해 예를 들어보겠다

 

처음에 stack에 abcd를 push한 상태에서 -> left: abcd |

P x가 입력되면 (커서 왼쪽에 x 삽입)

왼쪽 stack에 abcdx가 되야 하므로 

왼쪽 stack에 해당 문자 x를 push한다  -> left: abcdx |

 

다음으로 stack에 L을 입력하면 (커서를 왼쪽으로 한칸 이동)

왼쪽 stack에 abcd 오른쪽 stack에 x가 담겨야 되므로 ( abcd | x가 되야하므로) 

왼쪽 stack에 있는 값을 오른쪽 stack에 push해주고 왼쪽 stack에서는 pop해준다 -> left: abcd |  right: x

pop이나 peek을 해줄때 stack이 isEmpty상태인지 확인하는 것은 필수다 

 

다음으로 stack에 D를 입력하면 (커서를 오른쪽으로 한칸 이동)

다시 왼쪽 stack에 abcdx가 되야하므로 

오른쪽 stack에 있는 값을 왼쪽 stack에 push해주고 오른쪽 stack에서는 pop해준다 -> left: abcdx |

 

다음으로 stack에 B가 입력되면 (커서 왼쪽에 있는 요소 삭제)

왼쪽 stack에서 x를 삭제해줘야 하므로

왼쪽 stack에 있는 값을 pop시켜준다 -> left: abcd |

 

이러한 과정을 다 거치면

 

4. 왼쪽 stack과 오른쪽 stack에 문자가 담겨져있을텐데

 

for문으로 stack에 있는 내용을 출력할때 맨밑에 있는 요소부터 출력이 된다 

따라서 왼쪽 stack은 그대로 출력하면 되지만

오른쪽 stack은 위에서부터 출력이 되야하므로 왼쪽 stack으로 옮긴다

 

5. 왼쪽 stack으로 옮기고 왼쪽 stack의 내용을 출력하면 우리가 원하는 결과를 얻을 수 있다 

 

 

6. 이 문제는 시간초과 까지 고려해야 되는 문제로 BufferReader와 BufferWriter를 사용하였다 

 

Scanner 보다 BufferReader를 사용하는 습관을 기르자 

 

import java.util.*;
import java.io.*;
public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String str=bf.readLine();
		int n = Integer.parseInt(bf.readLine());

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

		for(int j=0;j<n;j++) {
			StringTokenizer st = new StringTokenizer(bf.readLine());
			String str1=st.nextToken();
			char ch1=str1.charAt(0);
			if(ch1=='P') {
				String str2=st.nextToken();
				char ch2=str2.charAt(0);
				left.push(ch2);
			}
			else if(ch1=='L') {
				if(!left.isEmpty()) {
					right.push(left.peek());
					left.pop();
				}
			}
			else if(ch1=='D') {
				if(!right.isEmpty()) {
					left.push(right.peek());
					right.pop();
				}
			}
			else if(ch1=='B') {
				if(!left.isEmpty())
					left.pop();
			}
		}

		while(!right.isEmpty()) {
			left.push(right.pop());
		}


		for(Character c:left)
			bw.write(c);
		bw.close();//스트림을 닫음
	}

}

 

느낀점:

코딩은 정말 한끝차이다 문제가 안풀릴때는 포기하고싶지만 문제가 풀릴때는 포기하고 싶은 감정을 다 잊게 만든다

결론은 이거다 포기하지 말자