문자열 폭발

문제

문자열 폭발

문제 설명

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

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

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

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

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

제한 사항

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.

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

첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.

입출력 예

입력	출력

| mirkovC4nizCC44
C4 | mirkovniz |
| 12ab112ab2ab
12ab | FRULA |

제출 코드

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

public class four9935 {
    public void solution() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String input = reader.readLine();
        String bomb = reader.readLine();

        if(input.length() < bomb.length()) {
            System.out.println(input);
            return;
        }

        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < input.length(); i++) {
            stack.push(input.charAt(i));
            if (input.charAt(i) == bomb.charAt(bomb.length() - 1)) {
                String temp = "";
                for (int j = bomb.length() - 1; j >= 0; j--) {
                    temp += stack.get(stack.size() - j - 1);
                }
                if (temp.equals(bomb)) {
                    for (int j = bomb.length() - 1; j >= 0; j--) {
                        stack.pop();
                    }
                }
            }
        }
        if (stack.isEmpty()) System.out.println("FRULA");
        else {
            for (Character ch : stack) {
                System.out.print(ch);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        new four9935().solution();
    }
}

근데 자꾸 인덱스 범위 오류,, 왜지?? 코드 다시 뜯어 보기 ㅜ

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

public class four9935 {
    public void solution() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String input = reader.readLine();
        String bomb = reader.readLine();
        int inputNum = input.length();
        int bombNum = bomb.length();
        char lastBomb = bomb.charAt(bombNum - 1);

        if (inputNum < bombNum) {
            System.out.println(input);
            return;
        }

        String temp = "";
        int size = 0;
        for (int i = 0; i < inputNum; i++) {
            char ch = input.charAt(i);
            temp += ch;
            size++;
            if (ch == lastBomb) {
                if (temp.contains(bomb)) {
                    temp = temp.substring(0, size - bombNum);
                    size -= bombNum;
                }
            }
        }

        if (temp.equals("")) System.out.println("FRULA");
        else System.out.println(temp);

    }

    public static void main(String[] args) throws IOException {
        new four9935().solution();
    }
}

이젠 또 메모리 초과,. 역시 스택을 써야 하는 듯

또 했더니 또 안 됨
if (stack.size() >= regexSize)

멍청이인가? 이걸 추가 안 함

스택에 쌓인 게 폭탄보다 커야지만 검사를 하지!!!! 그러니까 자꾸 인덱스 오류가 뜨지 ㅜ

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

public class four9935 {
    public void solution() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String line = reader.readLine();
        String regex = reader.readLine();
        int regexSize = regex.length();

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

        for (int i = 0; i < line.length(); i++) {
            stack.push(line.charAt(i));

            if (stack.size() >= regexSize) {
                boolean flag = true;
                for (int j = 0; j < regexSize; j++) {
                    if (stack.get(stack.size() - regexSize + j) != regex.charAt(j)) {
                        flag = false;
                        break;
                    }
                }

                if (flag) {
                    for (int j = 0; j < regexSize; j++) {
                        stack.pop();
                    }
                }
            }
        }

        StringBuilder builder = new StringBuilder();
        if (stack.isEmpty()) builder.append("FRULA");
        else {
            for(char ch : stack) {
                builder.append(ch);
            }
        }
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        writer.write(builder.toString());
        writer.flush();
    }

    public static void main(String[] args) throws IOException {
        new four9935().solution();
    }
}