[백준 9935] 문자열 폭발(Java)

문제 링크 : https://www.acmicpc.net/problem/9935

이 문제는 스택을 이용하여 풀 수 있습니다. 만약 스택을 사용하지 않고 일반적인 구현 방식으로 풀게 된다면 시간 초과 혹은 메모리 초과가 발생합니다. 따라서 스택에 문자를 하나씩 추가한 후 스택의 크기가 폭탄 문자열의 크기보다 크거나 같아질 경우 폭탄 문자열 개수만큼 스택을 탐색하여 모든 값이 같다면 해당 길이만큼 스택에서 pop하는 방식으로 문제를 풀 수 있습니다.

다음은 코드입니다.

import java.util.*;
import java.io.*;

class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String origin = br.readLine();
        String bomb = br.readLine();
        Stack<String> stack = new Stack<>();
        int cnt = bomb.length();

        for(int i=0;i<origin.length();i++){
            String curr = String.valueOf(origin.charAt(i));
            stack.push(curr);

            if(stack.size() >= cnt){
                boolean check = true;

                for(int j=0;j<cnt;j++){
                    if(!stack.get(stack.size()-cnt+j).equals(String.valueOf(bomb.charAt(j)))){
                        check = false;
                        break;
                    }
                }

                if(check) for(int j=0;j<cnt;j++) stack.pop();
            }
        }

        StringBuilder sb = new StringBuilder();
        if(stack.isEmpty()) System.out.println("FRULA");
        else{
            while(!stack.isEmpty()) sb.append(stack.pop());
            System.out.println(sb.reverse());
        }
    }
}