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

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

 

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

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

---

1.  아이디어

 

문자열을 Deque에 담으며 폭발 문자열의 마지막 글자를 발견하면 폭발 문자열인지 임시 Stack으로 판단하는 방식으로 해결했다.

---

2. 문제풀이

 

문자열의 각 문자를 일단 Deque에 담고 해당 문자가 폭발 문자열의 마지막 문자면 Deque에서 최근에 담은 문자들을 하나씩 Stack으로 옮기며 폭발 문자열이 맞는지 검증했다. 폭발 문자열이면 Stack을 초기화하면 되고 폭발 문자열이 아니면 Stack의 문자들을 다시 Deque에 넣어주는 과정을 반복하면 된다.

---

3. 코드

 

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();

        Deque<Character> deque = new ArrayDeque<>();
        Deque<Character> stack = new ArrayDeque<>();

        char[] input = br.readLine().toCharArray();
        char[] bomb = br.readLine().toCharArray();
        int len = bomb.length;

        for (char c : input) {
            deque.addLast(c);
            if (c != bomb[len - 1]) continue;

            boolean flag = true;
            for (int i = len - 1; i >= 0; i--) {
                if (deque.isEmpty()) {
                    flag = false;
                    break;
                }
                stack.push(deque.removeLast());
                if (stack.peek() != bomb[i]) {
                    flag = false;
                    break;
                }
            }

            if (flag) {
                stack.clear();
            } else {
                while (!stack.isEmpty()) {
                    deque.addLast(stack.pop());
                }
            }
        }

        if (deque.isEmpty()) {
            sb.append("FRULA");
        } else {
            while (!deque.isEmpty()) {
                sb.append(deque.removeFirst());
            }
        }

        bw.write(sb.toString());
        bw.flush();
    }
}

---

4. 후기