[백준] 9935번 : 문자열 폭발

9935번: 문자열 폭발

---

[문자열 / Stack(Array)]

# 풀이 요약

1. 문자열(origin)을 받아 char[ ] arr로 변환한다.

2. 폭발 문자열을 받아 char[ ] bomb으로 변환한다.

3. char[ ] stack을 준비한다. 이때 top = -1

 

4. arr의 한 문자씩 stack에 넣는다.

5. 만약 stack에 넣은게 bomb의 마지막 문자라면 bomb의 크기만큼 stack의 뒤로 가며 문자 비교

6 비교 결과 bomb을 동일하게 포함하고 있다면 문자열 폭파 (top -= bombSize)

(4~6) 반복

 

7. stack에 있는것 문자열로 변환 후 origin에 대입 후 결과 출력

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String origin = br.readLine();
        
        char[] bomb = br.readLine().toCharArray();
        int bombSize = bomb.length;

        char[] arr = origin.toCharArray();

        int top = -1;
        char[] stack = new char[1000001];
        
        for (char c : arr) {
            stack[++top] = c;

            //현재 문자가 폭발 문자열의 가장 마지막 꺼와 같다면 and stack의 크기가 폭발문자열 크기 이상이어야함
            if (stack[top] == bomb[bombSize - 1] && top >= bombSize - 1) {

                boolean flag = true;
                //한 문자씩 뒤로 가며 폭발 문자와 비교 (폭발 문자열과 다르면 flag = false)
                for (int j = bombSize - 1, z = 0; j >= 0; j--, z++)
                    if (stack[top - z] != bomb[j]) {
                        flag = false;
                        break;
                    }

                if (flag) //폭발 문자열이 존재하면 폭파 (top을 줄이면된다)
                    top -= bombSize;
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<=top; i++)
            sb.append(stack[i]);

        origin = sb.toString();

        System.out.println(origin.equals("")? "FRULA":origin);
    }
}