[백준/JAVA] 9935: 문자열 폭발

[백준/JAVA] 9935: 문자열 폭발

주어진 문자열에 폭발 문자열이 존재하면 그 문자열 부분을 없애버린다. 유의할 점은 폭발 문자열을 제거하여 새로 생긴 문자열에 또 폭발 문자열이 존재하면, 또 폭발이 일어나야 한다.

모든 폭발이 끝난 후에 남은 문자열을 출력하고, 남아있는 문자가 없다면 "FRULA"를 출력한다.

해당 문제는 스택 자료구조를 통해 풀 수 있는 문제이다. 주어진 문자열을 char 배열로 만들어 스택에 뒤에서부터 하나씩 push한다. 만약 스택의 top에 있는 문자가 주어진 폭발 문자열(bStr)의 가장 맨 앞의 문자와 같다면, 스택을 pop해나가면서 그 문자열과 비교한다. 비교하다가 다른 문자가 나온다면 서로 같지 않은 것이므로 문자열을 원상태로 복구해준다.

스택의 문자열을 복구해주는 과정에서 문제가 계속 생겼는데, for문이 j-1부터 0까지 돌기 때문에 비교를 아예 한번도 하지 않고 넘어가는 경우에도 복구를 해버려 결과가 이상해진 케이스였다.
이는 if (j == 0) break; 를 추가해주어서 해결하였다.

소스코드

---

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));
        char[] str = br.readLine().toCharArray();
        char[] bStr = br.readLine().toCharArray();

        Stack<Character> stack = new Stack<>();
        for (int i=str.length-1; i>=0; i--) {
            stack.push(str[i]);
            if (stack.size() >= bStr.length) {
                for (int j=0; j<bStr.length; j++) {
                    if (stack.peek().equals(bStr[j]))
                        stack.pop();
                    else {
                        if (j == 0)
                            break;
                        for (int k=j-1; k>=0; k--)
                            stack.push(bStr[k]);
                        break;
                    }
                }
            }
        }
        if (stack.isEmpty())
            System.out.println("FRULA");
        else {
            StringBuilder sb = new StringBuilder();
            int size = stack.size();
            for (int i=0; i<size; i++) {
                sb.append(stack.pop());
            }
            System.out.println(sb);
        }
    }
}