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

문제 설명

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

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

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

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

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

 

문제 풀이

처음에 저는 replaceAll을 통해 각 문자열들을 지워버렸습니다. 이랬을 때 제공되는 테스트케이스는 성립했지만 문제에서 주어진 조건은 충족시키지 못했습니다

 

이 문제에서 원하는 것은 문자열을 하나씩 읽으면서 폭발 문자열과 동일한 문자열이 생겼을 경우 제외시키는 것이기때문에 스택에 하나씩 저장하며 폭발 문자열과 같은지 비교해주면 해결됩니다.

풀이 코드

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

public class BOJ9935 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String str = br.readLine();
        String bomb = br.readLine();

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

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

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

                if (isSame) {
                    for (int j = 0; j < bomb.length(); j++)
                        stack.pop();
                }
            }
        }

        for (char ch : stack)
            sb.append(ch);

        System.out.println(sb.length() > 0 ? sb.toString() : "FRULA");
    }
}

 

<출처>

https://www.acmicpc.net/problem/9935

9935번: 문자열 폭발