[백준 알고리즘 풀이] 9935번 문자열 폭발

기본 아이디어는 문자열을 쌓다가 대상 비교 문자열 꼬다리 캐릭터와 현재의 캐릭터가 일치할 경우 뒤에서 부터 검사한 (backwarding) 후 제거하는거다. 애니팡 연속으로 터지는걸 생각하면 쉽다. 코드에서는 Stack을 하나 구현했는데 poll 대신에 그냥 index position만 변경해주는걸로 구현했다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
/*
 * 9935번 문자열 폭발
 */
public class Main {
 
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String input = br.readLine();
    String bomb = br.readLine();   
 
    Stack s = new Stack();
    for (int i = 0; i < input.length(); i++) {
      s.push(input.charAt(i));
 
      if (input.charAt(i) == bomb.charAt(bomb.length() - 1)) {
        s.checkAndRemove(bomb);
      }
 
    }
 
    s.printCurrent();
    br.close();
  }
 
  public static class Stack {
    private int top = 0;
    private char[] stack = new char[1000003];
 
    public void push(char x) {
      stack[top++] = x;
    }
 
    public boolean checkAndRemove(String bomb) {
      if (top < bomb.length())
        return false;
 
      int c = 0;
      boolean isTrue = true;
      for (int i = bomb.length() - 1; i >= 0; i--) {
        if (bomb.charAt(i) != stack[top - 1 - c]) {
          isTrue = false;
        }
        c++;
      }
 
      if (isTrue) {
        top = top - bomb.length();
        return true;
      } else {
        return false;
      }
    }
 
    public void printCurrent() {
      if(top == 0)
        System.out.println("FRULA");
      else {
        StringBuilder out = new StringBuilder();
        for (int i = 0; i < top; i++) {
          out.append(stack[i]);
        }
        System.out.println(out.toString());
      }
    }
  }
 
}