백준 [9935] 문자열 폭발 (JAVA)

문제

풀이

문자열 길이가 1000000까지 되기 때문에 폭발 문자열이 없을 때까지 계속해서 반복하여 replaceAll이나 완전 탐색을 사용하면 시간 초과가 발생한다.

 

1. 스택에 문자열의 문자를 담으면서 그때마다 폭발 문자열을 포함하는지 검사한다.
2. 이 때 스택의 길이가 폭발 문자열 보다 길거나 같아야 한다.
3. 폭발 문자열 길이만큼 반복하면서 stack.size - bombLen + j == bombStr.chatAt(j)인지 검사
4. 폭발 문자열과 일치하지 않으면 더이상 탐색을 진행하지 않고 다시 스택에 문자를 담는다.
5. 폭발 문자열과 일치하는 경우 폭발 문자열 길이 만큼 스택에서 pop 해준다.
6. 문자열 길이만큼 반복한다.
7. 스택이 비었으면 FRULA, 비어있지 않으면 스택의 값들을 출력한다.

정답코드

package com.baekjoon.data_structure.p9935;

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

        String inputStr = br.readLine();
        String bombStr = br.readLine();
        int bombLen = bombStr.length();

        Stack<Character> s = new Stack<>();

        for (int i = 0; i < inputStr.length(); i++) {
            // 스택에 입력 문자열 넣기
            s.push(inputStr.charAt(i));

            /*
             * 폭발 문자열과 길이가 같거나 긴 경우 폭발 문자열을 포함하는지 검사
             * 스택 사이즈가 폭발문자열보다 큰 경우 탐색을 계속하지만 폭발 문자열과 하나라도 일치하지 않는 경우
             * 탐색을 바로 중단하고 다음 입력 문자열을 스택에 푸시하고 검사
             */
            if (s.size() >= bombLen) {
                boolean findBomb = true;

                // 폭발 문자열 길이 만큼만 검사 이전 문자열들은 이미 폭발 문자열이 아님
                for (int j = 0; j < bombLen; j++) {
                    if (s.get(s.size() - bombLen + j) != bombStr.charAt(j)) {
                        findBomb = false;
                        break;
                    }
                }
                // 폭발 문자열을 발견했다면 폭발 문자열 길이 만큼 pop
                if (findBomb) {
                    for (int j = 0; j < bombLen; j++) {
                        s.pop();
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();

        if (s.size() == 0) {
            sb.append("FRULA");
        } else {
            for (int i = 0; i < s.size(); i++) {
                sb.append(s.get(i));
            }
        }

        System.out.println(sb);
    }
}