[BOJ] 9935. 문자열 폭발

패턴을 찾는 문자열 문제이다.

맨처음 패턴을 찾는 문제이기에 KMP를 사용하여 접근해보았다. 하지만 KMP가 반복적으로 호출되기때문에 시간초과가 발생한다. 따라서 다른방법을 사용해보았다. 스택을 사용하여 주어진 문자열의 앞에서부터 하나씩 스택에 집어넣고, 그 후 찾아야하는 패턴보다 같거나 큰길이를 스택이 가진다면 맨뒤에 스택의 맨뒤의 문자열이 패턴문자열과 똑같은지를 찾고, 똑같다면 제거해주는 방식의 알고리즘을 사용할 수 있다. 다만, 스택은 구조상 비효율적이기에 StringBuilder를 적용하여 풀어보았다.

package algostudy2;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main_bj_9935_문자열폭발_2 {
    static String input;
    static String pattern;
    static StringBuilder sb;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        input = br.readLine();
        pattern = br.readLine();
 
        sb = new StringBuilder();
 
        int patternLen = pattern.length();
 
        for (int i = 0; i < input.length(); i++) {
            sb.append(input.charAt(i));
            int sbLen = sb.length();
 
            if (sbLen >= patternLen) {
                boolean isFind = true;
 
                if (!sb.substring(sbLen - patternLen, sbLen).equals(pattern)) {
                    isFind = false;
                }
 
                if (isFind) {
                    sb.replace(sbLen - patternLen, sbLen, "");
                }
            }
        }
 
        if (sb.length() == 0) {
            System.out.println("FRULA");
        } else {
            System.out.println(sb.toString());
        }
 
    }
}