백준 9935번 : 문자열 폭발

 문제

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

9935번: 문자열 폭발

9935 문자열 폭발

 

 구현 방법

 

처음에는 스택을 안쓰고 while문을 돌려 처음부터 끝까지 계속 체크를 했습니다.

당연히 시간초과🥶

스택으로 다시 설계하였습니다.

 

 구현 코드

package BOJ.Gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class BOJ9935_문자열폭발 {
	static String input, search;
	static Stack<Character> stack, temp;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		input = br.readLine();
		search = br.readLine();
		stack = new Stack<>();
		temp = new Stack<>();
		for (int i=0;i<input.length();i++) {
			stack.add(input.charAt(i));
			if (temp.size()>0) temp.clear();
			if (stack.peek()==search.charAt(search.length()-1) && stack.size()>=search.length()){ // 남은 사이즈가 검색 문자 크기보다 클 때만 탐색
				for (int j=search.length()-1;j>=0;j--) {
					char now = stack.pop();
					temp.add(now); // 만약 틀렸을 때 순서대로 stack에 넣어주기 위한 temp 스택
					if (now!=search.charAt(j)) {
						while(!temp.isEmpty()) {
							stack.add(temp.pop());
						}
					}
				}
			}
		}
		if (stack.size()>0) {
			while(!stack.isEmpty()) sb.append(stack.pop());
			System.out.println(sb.reverse());
		} else System.out.println("FRULA");
	}
}

 

정답!