백준 1406번 <에디터>

백준 알고리즘 1406번

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

1406번: 에디터

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

아 진짜 어제 <단어 뒤집기> 쉬웠다 싶어서 도전한 <에디터>....

어제는 결국 시간 초과의 늪에서 빠져나오지 못했다. 으아아아아

오늘도 해보다가 안되서 구글링했다. 구글링 짱

---

1406번

입력으로 들어오는 문자열과 입력된 명령어를 순서대로 실행했을 때 남은 문자열을 출력해야한다.

이때 문자열의 길이는 10만까지 가능하고 입력될 명령어의 수는 50만까지 가능하다.

즉 입력만 60만까지 가능하다는 것이다. 

---

문제해결

입력이 되게 많이 들어와서 저번에 썼던 BufferedReader를 사용했다.

 

명령어 종류

L : 커서를 왼쪽으로 한 칸 옮긴다. (커서가 문장의 맨 앞이라면 무시)

D : 커서를 오른쪽으로 한 칸 옮긴다. (커서가 문장의 맨 뒤라면 무시)

B : 커서의 왼쪽에 있는 문자를 삭제한다. (커서가 문장의 맨 앞이라면 무시)

P $ : $라는 문자를 커서 왼쪽에 추가한다.

 

 

처음에는

커서의 위치를 index라는 int형 변수에 기억해둬서 풀도록 구현했다. 

그러기 위해서 StringBuffer의 delete메소드와 insert메소드를 사용했는데...

그게 O(n).... n은 명령어의 수... 나는 또 거기서 n만큼 반복문을 돌리니까....

결국 O(n^2).......... 시간 초과가 날 수 밖에 없었던 것이다....

 

그래서! Stack으로 풀기로 했다. 왼쪽 Stack, 오른쪽 Stack을 만들어서 푸는데 완전 획기적

구글링이 아니었다면 절대 생각하지 못했을 듯 하다.

 

처음 문자열을 왼쪽 Stack에 charAt()을 사용하여 다 넣어주고

명령어가 L이면

왼쪽 Stack이 비어있지 않으면 왼쪽 Stack에서 pop해서 나온 문자를 오른쪽 Stack에 push.

명령어가 D이면 

오른쪽 Stack이 비어있지 않으면 오른쪽 Stack에서 pop해서 나온 문자를 왼쪽 Stack에 push.

명령어가 B이면

왼쪽 Stack이 비어있지 않으면 왼쪽 Stack에서 pop

명령어가 P이면

같이 주어진 문자를 왼쪽 Stack에 push.

 

이렇게 구현해서! 제출했는데! 똑같이 시간초과가 나왔다....

 

그래서... 또 구글링을 했다.

 

이번에는 명령어를 입력받을 때가 시간이 오래 걸리는 것 같았다.

원래 명령어를 입력받을 때 

String str = br.readLine();

이렇게 계속 입력받았는데

 

구글링을 해서

StringTokenizer st = new StringTokenizer(br.readLine());
String str = st.nextToken();

이렇게 고쳐줬더니 시간 초과의 늪에서 빠져나올 수 있었다!!!!!!!

 

이때 명령어가 P이면

왼쪽 Stack에 push할 문자를 st.nextToken().charAt(0)으로 구할 수 있다.

(내가 Stack을 만들 때 Character형으로 만들어서 charAt(0)을 사용해야 헀다. 만약 String형이라면 사용하지 않아도 된다.)

---

코드

package bj1406;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

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

		int number = Integer.parseInt(br.readLine());
		int length = input.length();

		Stack<Character> left = new Stack<Character>();
		Stack<Character> right = new Stack<Character>();

		for (int i = 0; i < length; i++) {
			left.push(input.charAt(i));
		}

		for (int i = 0; i < number; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String str = st.nextToken();
			if (str.equals("L")) {
				if (!left.isEmpty()) {
					char leftPop = left.pop();
					right.push(leftPop);
				}

			} else if (str.equals("D")) {
				if (!right.isEmpty()) {
					char rightPop = right.pop();
					left.push(rightPop);
				}
			} else if (str.equals("B")) {
				if (!left.isEmpty()) {
					left.pop();
				}
			} else { // P $
				left.push(st.nextToken().charAt(0));
			}
		}

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

		while (!right.isEmpty()) {
			System.out.print(right.pop());
		}
        
//		int leftSize = left.size();
//		int rightSize = right.size();
//		for(int i = 0; i < leftSize; i++) {
//			char leftChar = left.pop();
//			sb.insert(0, leftChar);
//		}
//		for(int i = 0; i < rightSize; i++) {
//			char rightChar = right.pop();
//			sb.append(rightChar);
//		}

	}

}

---

결과

---

ㅎㅎ

사실 출력할 때 for문을 이용해서 출력하는 걸로 먼저 구현했는데 시간초과가 또 떠서ㅋㅋㅋㅋㅋㅋㅋㅋㅋ

while문으로 바꿔봤는데 됐다.

while문이 맘에 들었나봐... 다행이다... 성공할 수 있어서... 너무 행복해....

 

https://seunghee114-blog.tistory.com/76?category=879824

for문과 while문

https://seunghee114-blog.tistory.com/77

자바 StringTokenizer