백준 9935 (문자열 폭발)

문제

---

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

• 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
• 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
• 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

 

 

 

풀이

---

스택과 문자열처리에 관한 문제다.

스택을 직접 사용하지 않고 스택의 자료구조 방식만 이용한 문제다.

 

Stack 의 기본 구조는 후입선출이다.

결과를 저장할 배열을 할당 받고

폭탄 문자와 뒤부터 비교를 하여 맞다면 폭탄문자의 길이만큼 인덱스를 삭제한다.

그러고 뒤의 문자를 덮어쓰며 푸는 방식이다.

 

<전체 코드>

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;

import javax.management.Query;

import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

public class Main {

	static StringBuilder sb = new StringBuilder();
	static int[][][] LCS;
	
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        
        char[] string = bufferedReader.readLine().toCharArray();
        char[] bomb = bufferedReader.readLine().toCharArray();
        
        char[] ans = new char[1000001];
        int size = 0;
        for(int i = 0 ; i < string.length ; i++) {
        	ans[size++] = string[i];
        	
        	int bomb_index = bomb.length - 1;
        	if(string[i] == bomb[bomb_index]) {
        		boolean isContain = true;
        		
        		int index = size - bomb.length;
        		if(index >= 0 ) {
	        		for(int j = size - 1; j >= index ; j--) {
	        			if(ans[j] == bomb[bomb_index--]) {
	        				isContain = true;
	        			}
	        			else {
	        				isContain = false;
	        				break;
	        			}
	        		}
	        		if(isContain)
	        			size = size - bomb.length;
        		}
        	}
        	
        }
        
        if(size == 0)
        	sb.append("FRULA");
        else {
        	for(int i = 0 ; i < size ; i++) {
        		sb.append(ans[i]);
        	}
        }
        
               
        System.out.println(sb);
    }
        
}