BOJ_9935 : 문자열 폭발

👉 문제링크

9935번: 문자열 폭발

---

---

🔸 문제 분석 🔸

• 기본 문자열과 폭발 문자열이 입력된다.
• 기본 문자열에서 폭발 문자열 부분이 폭발하며 지워지고, 남은 문자열은 다시 이어 붙는다.
• 더 폭발할 문자열이 남지 않았을 상태의 문자열을 출력한다.
  • 남은 문자가 없으면 "FRULA"를 출력한다. 

🔸 문제 풀이 🔸

• 문자열의 길이가 100만이기 때문에 O(n^2) 미만의 알고리즘을 사용해야 한다.
  • 반복문 한 번에 계산할 수 있도록 한다.
• 새로운 문자열이 생기면 메모리 문제가 생길 수 있으므로, 문자 배열의 스택 구조로 폭발 문자열인지 확인한다.
  • 폭발 문자열의 마지막 문자이면, 스택에서 폭발 문자열 크기만큼 꺼내서 확인한다.
  • 폭발하면 지우고, 폭발하지 않으면 다시 스택에 넣어준다.
• 스택에 남은 문자열을 출력한다.

🔸 코드 🔸

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

public class Main {
    private static Stack<Character> stack;
    private static char[] boom;

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

        char[] chars = br.readLine().toCharArray();
        boom = br.readLine().toCharArray();

        int last = boom[boom.length - 1];

        stack = new Stack<>();

        for (char c : chars) { // 입력된 문자열 검사
            if (stack.size() >= boom.length - 1 && c == last) { // 폭발 문자열의 마지막 문자와 같으면 폭발되는지 확인
                if (!boomCheck()) { // 안터졌으면 지금 문자 스택 넣기
                    stack.push(c);
                }
            } else {
                stack.push(c);
            }
        }

        if (stack.size() == 0) {
            bw.write("FRULA");
        } else {
            StringBuilder sb = new StringBuilder();
            while (!stack.isEmpty()) sb.append(stack.pop());
            bw.write(sb.reverse().toString());
        }
        bw.flush();
    }

    private static boolean boomCheck() { // 폭발 검사 : 터지면 삭제
        char c;
        for (int i = boom.length - 2; i >= 0; i--) {
            if (stack.isEmpty()) {
                for (int j = i + 1; j < boom.length - 1; j++) {
                    stack.push(boom[j]);
                }
                return false;
            } else if ((c = stack.pop()) != boom[i]) { // 폭발 문자열 아님 : 복구
                stack.push(c);
                for (int j = i + 1; j < boom.length - 1; j++) {
                    stack.push(boom[j]);
                }
                return false;
            }
        }
        return true;
    }
}

🔸 코드 해석 🔸

• 기본 문자와 폭발 문자열을 입력받아 char배열로 저장한다.
• 입력된 문자열을 하나씩 검사해 폭발 문자열의 마지막 문자가 나오면 boomCheck() 메서드에서 폭발을 확인한다.
  • 폭발하면 지워주고, 폭발하지 않으면 해당 문자를 stack에 추가한다.
• boomCheck() 에서 stack의 문자를 하나씩 꺼내 폭발 문자열과 비교한다.
  • 스택이 모두 비어버리거나 일치하지 않는 경우가 생기면, 복구한다.
  • 폭발 문자열이 완성되면 복구하지 않고 true를 반환한다.
• 최종 stack에 남은 문자열을 확인해 문자열을 출력한다.

---

🔸 end 🔸

• 문자열 처리 문제여서 쉽게 봤다가 많이 틀리게 되었다.
  • 첫 시도는 폭발 후 문자열을 StringBuilder로 모아서 다시 chars를 갱신하는 방식인데, 새로운 문자열이 계속 생성되어서 그런지 메모리 초과가 났다.
  • 두번째는 폭발 문자열이 남지 않을 때 까지 반복문을 다시 도는데, O(n^2)라서 시간 초과가 났다.
  • 세번째는 스택 구조로 변경했는데 폭발 문자열의 크기가 2이하거나, 스택이 비었을 경우 등의 예외처리가 부족해서 틀렸다.
• 오랜만에 스택 문제여서 신선했던 것 같다.