백준 9935번 - 문자열 폭발 (java)

💡 문제 링크

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

 

💡 아이디어

처음에는 슬라이딩 윈도우 형태로 풀이를 하였으나 시간 초과가 났다.

슬라이딩 윈도우를 사용해도 부분문자열을 제거하는 과정 때문에 O(n)이 곱해져 시간 초과가 난다.

결국 다른 풀이를 참고하였고, 스택을 사용해야 하는 것을 알았다.

 

1. 문자열의 문자를 하나씩 스택에 push 한다.

2. 스택의 크기가 폭발 문자열의 길이 이상이 되고, 마지막 글자가 폭발 문자열의 마지막 글자와 일치한다면

3. (폭발 문자열 길이만큼의)가장 위쪽의 문자들을 체크한다. 폭발 문자열과 일치하는지.

     3-1. 일치하면 해당 문자들을 스택에서 제거한다.

     3-2. 일치하지 않으면 1번으로 가서 다음 문자를 push한다.

4. stack에 남은 문자가 있으면 그대로 출력하고, 남은 문자가 없으면 FRULA를 출력한다.

 

💡 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class BOJ_G4_9935_문자열폭발 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        String bombStr = br.readLine(); //폭발 문자열
        int strLen = str.length();
        int bombLen = bombStr.length(); //폭발 문자열 길이
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < strLen; i++) {
            stack.push(str.charAt(i));
            
            //스택 크기가 폭발 문자열의 길이와 같거나 크고 + 마지막 글자가 폭발 문자열의 마지막 글자와 일치하는 경우 -> 문자열 비교
            if (stack.size() >= bombLen && str.charAt(i) == bombStr.charAt(bombLen - 1)) {
                boolean hit = true;
                //문자열 비교
                for (int j = 0; j < bombLen; j++) {
                    if (stack.get(stack.size() - bombLen + j) != bombStr.charAt(j)) { //문자열 불일치
                        hit = false;
                        break;
                    }
                }
                if (hit) { //문자열 일치하는 경우
                    for (int j = 0; j < bombLen; j++) {
                        stack.pop();
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        if (stack.isEmpty()) System.out.println("FRULA");
        else {
            while (!stack.isEmpty()) {
                sb.append(stack.pop());
            }
            System.out.println(sb.reverse());
        }
    }
}