[BOJ] 9935 문자열 폭발 (JAVA)

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

9935번: 문자열 폭발

전체 문자열을 대상으로 contains 등을 이용하여 찾아서 없애려고 하면 시간초과가 날 겁니다.

Stack을 이용하여 문자열을 한 번 만들어 낼 때 폭발 문자열을 제외하고 만들게 했습니다.

 

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

public class Main {
    
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {

        String str = br.readLine(); // 입력 문자열
        String cut = br.readLine(); // 폭발 문자열

        Stack<Character> stack = new Stack<>();
        int size = cut.length() - 1;
        char start = cut.charAt(0);

        for (int i = str.length() - 1; i >= 0; i--) {

            char c = str.charAt(i);
            stack.push(c);

            if (c == start && size < stack.size()) {

                Stack<Character> temp = new Stack<Character>();

                for (int j = 0; j <= size; j++) {

                    char strC = stack.pop();
                    char cutC = cut.charAt(j);
                    temp.push(strC);

                    if (strC != cutC) {
                        while (!temp.isEmpty()) {
                            stack.push(temp.pop());
                        }
                    }

                }

            }

        }

        if (stack.isEmpty()) sb.append("FRULA");
        else {
            while (!stack.isEmpty()) {
                sb.append(stack.pop());
            }
        }

        System.out.print(sb.toString());

    }

}