백준 9935번 - 문자열 폭발 / Java

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

9935번: 문자열 폭발

폭발 문자열이 있으면 주어진문자열에서 빼는 문제. 연쇄 폭발처리 방법을 생각하는 것때문에 적지 않은 시간이 걸렸다.

연쇄 폭발처리를 하기위해 두개의 스택을 이용해서 풀었다. 문자열처리를 하다가 폭발문자열이 나올경우 폭발문자열을 없애고 폭발문자열의 길이만큼 다시 앞으로 돌아가서 처리를 했다. 폭발문자열을 없애는 과정에서 다시 폭발문자열이 생길수 있기때문

 

알고리즘

 

첫번째 스택 : stack1, 두번째스택 : stack2

1. stack1에 문자열을 입력받는다

2. stack2에 stack1에서 pop한것을 push한다 반복하면서 폭발문자열이 나오는지 확인한다

3. 폭발문자열이나올경우 폭발문자열의 길이만큼 stack2를 pop하고 폭발문자열의 길이만큼 stack2에서 팝한것을 stack1에 푸쉬

4. 2~3을 끝날때까지 반복한다

 

소스코드

/*
 * BOJ9935
 * 2020.01.21
 * Hyeonseong
 */
import java.util.*;
public class BOJ9935 {
 
    public static void main(String[] args) {
        Solution s = new Solution();
    }
}
class Solution{
 
    public Solution() {
        Scanner scan = new Scanner(System.in);
        String str = scan.next();
        String bomb = scan.next();
        Stack<Character> stack1 = new Stack<Character>();
        Stack<Character> stack2 = new Stack<Character>();
        for(int i=0;i<str.length();i++) {
            stack1.push(str.charAt(i));
        }
        int idx = 0;
        while(!stack1.isEmpty()) {
            stack2.push(stack1.pop());
            if(stack2.peek()==bomb.charAt(bomb.length()-(idx+1))) { //폭발문자열과 문자가같으면
                idx++;
            }
            else {
                idx = 0;
                if(stack2.peek()==bomb.charAt(bomb.length()-(idx+1))) { // 하나라도 다르면 초기화
                    idx++;
                }
            }
            if(idx==bomb.length()) { // 폭발문자열이 나오면
                for(int i=0;i<bomb.length();i++) {
                    stack2.pop(); // 길이만큼 빼주고
                }
                for(int i=0;i<bomb.length();i++) {
                    if(!stack2.isEmpty()) {
                        stack1.push(stack2.pop()); // 재검사를 위해 폭발문자열길이만큼 stack1에 다시푸쉬
                    }
                    else {
                        break;
                    }
                }
                idx = 0;
            }
        }
        if(stack2.isEmpty()) {
            System.out.println("FRULA");
        }
        else {
            StringBuilder sb = new StringBuilder();
            while(!stack2.isEmpty()) {
                sb.append(stack2.pop());
            }
            System.out.println(sb.toString());
        }
    }
}