[백준] 9935번 - 문자열 폭발 (Gold 4)

문제 링크

백준 9935번 - 문자열 폭발 (Gold 4)

문제 설명

주어진 문자열에 폭발 문자열이 포함되어 있다면, 이를 전부 폭파시킨다.
남은 문자열에도 폭발 문자열이 포함되어 있다면, 폭파시킨다.
이 과정을 계속 반복했을 때 최종적으로 남은 문자열을 출력하는 문제이다.
만약 최종 문자열이 비어있다면, FRULA를 출력한다.

정답 코드 및 설명

문자가 폭발할 여지가 있는 경우에 스택에 하나씩 담아둔다.
폭발해야한다면 그 부분을 날려버리고, 폭발하지 않는다면 스택을 비우고 스택에 쌓여있던 문자들을 출력한다.
폭발할 여지가 있다는 것은, 폭발 문자열의 첫 문자와 같은 문자거나 바로 앞 문자와 이어지는 폭발 문자열을 담고 있을 때이다.

말로 표현하면 이상하니 예시를 들어보자.
주어진 문자열이 “aabccd”이고 폭발 문자열이 “abc”인 경우를 생각하자.

1. a는 폭발 문자열의 시작 문자이므로, 폭발 가능성이 있다. 스택에 담는다.
2. 다음 a도 폭발 문자열의 시작 문자이다. 스택에 담는다.
3. b는 폭발 문자열의 두번째 문자이고, 바로 앞이 폭발 문자열의 시작 문자이므로 스택에 담는다.
4. c는 폭발 문자열의 세번째이자 마지막 문자이다. 스택에 담고 abc 세 문자를 날려버린다.
5. 다음 c는 스택의 제일 뒤 원소가 a인데, 폭발 문자열에서 a와 이어지지 않는다.
   스택을 비우고 스택에 있던 a와 현재 문자인 c를 정답에 추가한다.
6. d는 폭발 문자열의 원소가 아니다. 스택이 비어있으므로 정답에 d를 추가한다.
7. 처리가 모두 끝났다. 최종적으로 구해진 정답 문자열은 “acd”로 비어있지 않다.
   그대로 “acd”를 출력한다.

이를 java 코드로 구현하면 아래와 같다.
폭발 문자열에서 이어진다는 것을 구현하기가 까다로워서, 폭발 문자열에서 몇번째 문자인지를 스택에 추가했다.
시간 소모를 줄이기 위해, 스택에서 일일히 문자를 추가하지 않고 현재 스택에 대응되는 문자열 temp를 활용했다.

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringBuilder temp = new StringBuilder();

        String str = br.readLine();
        String bomb = br.readLine();
        int bombLength = bomb.length();
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < str.length(); i++) {
            char curr = str.charAt(i);
            int currBomb = -1;
            if (!stack.isEmpty())
                currBomb = stack.peek();
            // 폭발 문자열이 시작되거나 이어짐 : 스택에 추가
            if (curr == bomb.charAt(0) || curr == bomb.charAt(currBomb + 1)) {
                int currIndex = 0;
                if (curr == bomb.charAt(currBomb + 1))
                    currIndex = currBomb + 1;
                stack.add(currIndex);
                temp.append(curr);
                // 폭발 문자열이 완성된 경우 폭파
                if (currIndex == bombLength - 1) {
                    for (int j = 0; j < bombLength; j++)
                        stack.pop();
                    temp.delete(temp.length() - bombLength, temp.length());
                }
                continue;
            }
            // 폭발 문자열이 이어지지 않으면 스택 비우고 최종 문자열에 추가
            sb.append(temp).append(curr);
            stack.clear();
            temp = new StringBuilder();
        }
        // 끝까지 탐색하고도 스택에 원소가 남았다면
        sb.append(temp);

        String ans = sb.toString();
        // 남아있는 문자가 없다면
        if (ans.isEmpty())
            ans = "FRULA";
        bw.write(ans);
        bw.close();
    }
}

문제 풀고나서 정답 코드를 보다보니, 훨씬 쉬운 방법이 있었다.
현재 문자가 폭발 문자열의 마지막 문자인지 확인하고 맞으면 폭발 문자열의 길이만큼 비교하면 된다.
스택 같은 자료구조를 아예 모르고 단순 문자열로도 처리 가능한 문제였다.