[BOJ] 9935 문자열 폭발 - JAVA

1. 문제

9935번: 문자열 폭발

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

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

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

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

---

2. 풀이

1.  stack으로 문자열을 하나씩 저장하다가 폭발 문자열의 끝 문자열과 동일하다면 remove메서드를 호출한다.

2.  remove메서드는 stack의 끝부터 하나씩 폭발 문자열과 비교하며 pop시킨다. 만약 중간에 stack이 비었거나 폭발문자열과 다른 문자열이 stack에 있다면 반복을 멈추고 해당 위치+1부터 폭발 문자열 끝까지 다시 push한다.

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

public class BOJ_9935_문자열폭발 {
   static Stack<Character> stack = new Stack<>();
   static char[] bomb;
   static int len;
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

      char[] str = in.readLine().toCharArray();
      bomb = in.readLine().toCharArray();
      len = bomb.length;

      for(char ch:str){
         stack.push(ch);
         if(ch==bomb[len-1]){
            remove();
         }
      }

      if(stack.size()==0) {
         System.out.println("FRULA");
         return;
      }

      StringBuilder answer = new StringBuilder();
      while(!stack.empty()) answer.append(stack.pop());
      System.out.println(answer.reverse());
   }

   public static void remove(){
      for(int i=len-1;i>=0;i--){
         if(stack.empty() || stack.peek()!=bomb[i]){
            for(int j=i+1;j<len;j++){
               stack.push(bomb[j]);
            }
            return;
         }else{
            stack.pop();
         }
      }
   }
}

---

3. 결과

첫번째 코드는 이거였는데, 어쩐지 너무 간단하다 싶었다.. 메모리제한을 신경써서 봐야겠다.

(사실 힌트를 보기 전까지는 이 문제를 stack으로 풀거라고 상상못했다. 더 공부해야겠다 ..!)

import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String str = in.readLine();
		String bomb = in.readLine();
		while(str.contains(bomb)){
			str = str.replaceAll(bomb,"");
		}
		if(str.length()==0) System.out.println("FRULA");
		else System.out.println(str);
	}

}

두번째로 틀린 emptystack은 빈 스택일 때 peek()메서드가 에러난다는 걸 고려하지 않아서였다. 그 부분만 수정해주니 맞았다.