[9935] 문자열 폭발

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

---

import java.util.Scanner;

// 9935 문자열 폭발
public class Main {
	static char[] stack;
	static String first, second;
	static int top=0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		first = sc.next();
		second = sc.next();
		char[] f = first.toCharArray();
		char[] s = second.toCharArray();

		char last = s[s.length - 1];
		stack = new char[f.length];
		
		Outter: for (int i = 0; i < f.length; i++) {
			
			stack[top++] = f[i];
			
			if (f[i] == last) {
				int len = s.length;
				int x = top;
				for (int j = len - 1; j >= 0; j--) {
					if(x-1<0) continue Outter;
					if (stack[x - 1] != s[j]) continue Outter;
					else x--;
				}
				top -= len;
			}
		}

		if (top==0)
			System.out.println("FRULA");
		else {
			for (int i = 0; i < top; i++) {
				System.out.print(stack[i]);
			}
		}

	}
}

---

처음엔 첫번째 문자열 first 안에 두번째 문자열이 포함되지 않을 동안 while(first.contains(second)) 처럼 while 문을 돌면서 second 문자열을 삭제하고 문자열을 붙이고 하는식으로 문제를 풀었지만, 첫번째 문자열의 길이가 100만이기 때문에 시간초과가 났다.

그래서 어떻게 풀지 다시 생각해보다가 예전에 풀어서 정리했던

탑 https://daily-life-of-bsh.tistory.com/17?category=784825 문제가 생각났다. 문자열을 탐색하면서 동시에 stack에 넣을지 말지 판단하는 탑 문제와 비슷한 방식으로 풀게 되었는데, 처음에는 자바에서 제공하는 Stack 클래스를 사용해서 문제를 풀었는데, 시간초과가 났다. 그래서 스터디 하는 친구가 보여준 코드를 보고 Stack클래스를 사용하지 않고 내가 Stack을 만들어서 풀었는데, 해결되었다. 왜 Stack 클래스를 사용하면 시간초과가 뜨고, 내가 직접만들어서 사용하면 시간초과가 안뜨는지 잘 모르겠다. 아마 Stack의 elementAt함수를 써서 그런것 같다.

<문제 풀이>

1. 두번째 문자열의 마지막문자를 last라는 char 변수에 저장한다. 왜냐하면 첫번째 문자열의 처음부터 끝까지 stack에 넣다가 두번째 문자열의 마지막문자 last를 만나면 삭제 할지 안할지 판단하기 위해서 이다.

2. 첫번째 문자열을 stack에 계속 넣다가 last 변수와 같은 문자열을 만나게 되면, 이제 두번째 문자열이 포함되어있는지 검사하기 위해서 그동안 stack에 쌓인 값과 두번째 문자열의 뒤부터 검사하게 된다.

3. 만약에 두번째 문자열과 다르다면 다시 처음으로 돌아가서 계속해서 첫번째 문자열을 stack에 쌓으면 된다.

4. 만약에 두번째 문자열과 같은것이 stack에 포함되어 있었다면 top에서 두번째 문자열의 길이를 빼준다. top에서 두번째 문자열의 길이를 빼주는 이유는 그동안 stack에 쌓여있는 두번째 문자열을 pop하는 효과랑 같다.

5. 반복문을 빠져나오면 top을 검사해서 만약에 0이라면 비어있는 것이기 때문에 "FRULA"를 출력하고 아니라면 stack에 있는 문자열을 출력한다.