[백준]9935번 문자열 폭발

9935번: 문자열 폭발

• 폭발하면, 그 문자는 문자열에서 사라짐 + 남은 문자열은 합쳐진다.

1. IF, 폭발문자열이 존재 → [모든 ] 폭발 문자열이 폭발.
   1. 남은 문자열을 [순서대로 이어붙여 ] 새로운 문자열 생성
2. 새로 생긴 문자열에 폭발 문자열이 포함되어있을 수도 있다
   1. 이어붙인 결과로 생기는 것이니 , 최대, 이전에 폭발한 문자열의 개수 만큼 이려나..
3. 폭발은 [ 폭발 문자열이 문자열에 없을 때 까지 ] 계속된다.

상근이는 모든 폭발이 끝난 후, [ 어떤 문자열이 남는지 ] 구해 보려 한다.

• 남아있는 문자가 없는 경우는 →"FRULA"를 출력
• 폭발 문자열은 "같은 문자를 두 개 이상 포함 X"
  • 따라서, abababab 일 때 폭발문장려은 aba 이런 경우는 없게 된다 (만약 그런경우,bb이거나 abbab가 남아버리거나...이런 요상한 경우들이 생길 수도 있으니 그런 것 같기도 하다 )
    

---

• 문자열의 길이는 1이상 1백만 이하
• 폭발 문자열의 길이는 1이상, 36이하
• 두 문자열은 "알파벳소문자,대문자"+"0~9"로만 이루어져있다.

---

예시를 보자

mirkovC4nizCC44
C4
==============첫 번째 폭발
mirkovnizC4
=============== 두 번째 폭발
mirkovniz

풀이 생각

(1:20....)

• 일단.. 한 번 폭발 시킬 때, [ 모든 ] 폭발 문자열이 폭발하게 된다는 것에 유의하자.
• 단순하게 전체탐색으로 매 번 폭발시키고 결과에서 또 폭발시킨다면...
  • 매 번 폭발에서는 한개만 폭발하는데, 그결과로 매 번 폭발할 문자열이 생길수가 있다.
  • 이 경우 100만 x ...을 하게 될 수가 있다.
  • 시간초과가 나올 것이다.
• 두 번째 생각 : stack 을 써 보면 어떨까
  • 이 때 기준은, 폭발문자열의 마지막 글자와 같은 글자를, encounter 할 때 마다, stack에서 n-1개의 글자를 순서대로 pop하며, 폭발 문자열과 같은지 확인한다. => 그렇다면 100만개를 계속해서 반복 확인을 하게 되지는 않을 것 같다
    • stack에 더이상 글자가 없으면 fail과 같은 경우다. 이제까지 pop한 것을 다시 넣어야 한다
    • 중간에라도 fail하면( 해당 번째의 글자와 폭발문자열상의 글자가 같지 않으면 ) 이제까지 pop한 것을 다시 넣어야 한다.....
    • 성공하는 경우 그렇게, target 폭발 문자열 만큼의 pop을 stack으로부터 하는 것을 완료하면 된다.

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

public class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StringTokenizer st;
    public static StringBuilder sb = new StringBuilder("");
    public static String src,target;
    public static Deque<Character> stack = new LinkedList<>();
    public static void setting() throws IOException {
        src = br.readLine();
        target = br.readLine();
    }
    public static void solve() throws IOException {
        for(int j=0;j<src.length();j++) {
            if(src.charAt(j)==target.charAt(target.length()-1)){
                // iterate해 나간다. target.charAt(target.length()-1)) 에 있는 character와 비교하여, 같은 순간에는, stack에서 순차적으로 n-1개를 꺼낸다
                // 꺼내는 도중에, target(i)와 같지 않다면 -> 다시 stack에 넣어줘야 한다.
                for (int i = target.length() - 2; i >= 0; i--) {
                    if(stack.isEmpty()){
                        // fail
                        // 다시 넣어주는 과정:repush
                        for (int re = i + 1; re < target.length(); re++) stack.add(target.charAt(re));
                        break;
                    }
                    if (stack.getLast() != target.charAt(i)) {
                        // fail
                        // 다시 넣어주는 과정 : repush 
                        for (int re = i + 1; re < target.length(); re++) stack.add(target.charAt(re));
                        break;
                    } else {
                        // pop ( 현재 글자는 성공 -> pop ) 
                        stack.pollLast();
                    }
                }
            }else{
                stack.add(src.charAt(j));
            }
        }
        while(stack.isEmpty()==false){
            sb.append(stack.pollFirst());
        }
        if(sb.length()==0)sb.append("FRULA");
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
    public static void main(String[] args)throws IOException {
        setting();
        solve();

    }
}