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

백준 9935 문자열 폭발

 

9935번: 문자열 폭발

 

 

문제 설명

 

 - 상근이는 문자열에 폭발 문자열을 심어 놓았다.

 

 - 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

 

 - 문자열 폭발 과정은 다음과 같다.

   1. 문자열이 폭발 문자열을 포함하고 있는 경우에는 모든 폭발 문자열이 폭발하고,

      남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.

 

   2. 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수 있다.

 

   3. 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

 

 - 상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구하려 한다.

   남아있는 문자가 없는 경우에는 "FRULA"를 출력한다.

 

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

 

 

 

---

 

입력 값

 

 - 첫째 줄에 문자열이 주어진다.

   문자열은 1보다 크거나 같고, 1,000,000 보다 작거나 같다.

 

 - 둘째 줄에 폭발 문자열이 주어진다.

   폭발 문자열의 길이는 1보다 크거나 같고, 36보다 작거나 같다.

 

 - 두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0 ~ 9 로만 이루어져 있다.

 

---

 

 

예제

 

---

 

 

문제 분석

 

 - 이 문제를 보고 가장 간단하게 생각할 수 있는 방법은 폭발 문자열이 없을 때 까지 계속해서 탐색하는 방법이다.

 

 - 1. 처음 N개의 문자를 모두 살펴봐서 폭발 문자열을 모두 제거한다. 

   2. 그 이후 남은 문자열을 바탕으로 1을 반복한다.

   3. 모든 폭발 문자열을 제거한 후 답을 리턴한다.

 

 - 위 방법 같은 경우, 기준 문자열이 최대 길이가 100만이 되는 경우 100번 반복되더라고 1억이 된다.

   하지만, 그것보다 많은 수가 반복 될 수 있기 떄문에 불가능한 방법이다.

 

 - 예를 들어, aaaa.....abbbb.....bbbb 라는 a가 앞에서 50만개, b가 뒤에서 50만개가 있는 기준 문자열이 존재한다.

   폭발 문자열을 ab라고 하는 경우, 폭발은 약 50만번이 일어나고, 이 폭발 떄마다 100만의 모든 문자를 탐색한다.

   즉, ( 100만 + 99만9998 + ... + 2 + 0 ) 가 되기 때문에 불가능해진다.

 

 - 그렇다면 어떻게 풀어야 할까?

 

 - 기준 문자열의 길이는 최대 100만이기 떄문에 O(N)의 시간 복잡도 혹은 O(NlogN) 의 시간복잡도가 필요하다.

 

 - 문자열 폭발이 일어나는 경우 해당 문자열은 사라지고, 남은 문자열을 순서대로 이어붙인다.

 

 - 즉, 현재 위치에서 폭발이 일어나게 된다면, 새로운 문자열은 해당 위치에서 생기는 것이다.

   그렇기 떄문에 그 이전 위치는 탐색할 필요가 없다.

 

 - 그렇다면, 폭발이 일어나고 어떻게 새로운 문자열이 폭발 문자열인지 판단할 수 있을까?

 

 - 이것은 스택을 이용하면 간단하게 구현할 수 있다.

 

 - 1. 기준 문자열을 순차적으로 탐색하면서 스택에 넣는다.

   2. 스택의 top이 폭발 문자열의 마지막 문자열이라면, 스택에서 하나씩 꺼내어 폭발 문자열과 비교한다.

   3. 폭발 문자열과 다르다면, 다시 스택에 넣고 그 다음을 살펴본다.

   4. 폭발 문자열과 같다면, 해당 문자열을 제거하고 그 다음을 살펴본다.

 

 

  - 기준 문자열이 abcd이고, 폭발 문자열 bc인 경우 스택에 c까지 넣게 되면, 폭발 문자열 길이 만큼 꺼내어 비교한다.

  - 그 이후 일치하기 때문에 폭발 문자열 제거 후  d를 넣는다.

---

 

 

소스 코드

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

// https://www.acmicpc.net/problem/9935
// 문자열 폭발
public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        char original[] = bf.readLine().toCharArray();

        char bombs[] = bf.readLine().toCharArray();

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

        for(int i=0;i<original.length;i++){

            char nowChar = original[i];

            if(nowChar == bombs[bombs.length-1] && result.size() >= bombs.length-1){
                Stack<Character> st = new Stack<>();
                st.add(nowChar);
                boolean isBomb=true;
                for(int j = bombs.length-2;j>=0;j--){
                    if(result.peek() == bombs[j]){
                        st.add(result.pop());
                    }
                    else{
                        isBomb=false;
                        break;
                    }
                }

                if(!isBomb){
                    while(!st.isEmpty()){
                        result.add(st.pop());
                    }
                }

            }
            else{
                result.add(nowChar);
            }
        }

        StringBuilder sb = new StringBuilder();

        while(!result.isEmpty()){
            sb.append(result.pop());
        }

        sb.reverse();

        String answer = sb.toString();

        if(sb.length()==0){
            answer="FRULA";
        }

        System.out.println(answer);

    }
}