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

문자열 문제입니다.

문자열과 폭발 문자열이 주어집니다.
문자열에 폭발 문자열과 같은 단어가 있다면 해당 문자를 지웁니다.
위의 방식을 반복하여 최종적으로 남는 문자열을 출력하는 문제입니다.

문자열의 모든 위치에서 폭발 문자열이 있는지 비교하게 된다면 O(N^2)의 시간이 걸리게 됩니다.
현재 인풋으로 받는 문자열의 최대 길이가 1,000,000 이므로 O(N^2)으로 풀게 된다면 시간초과가 발생하게 됩니다.

문자열을 차례대로 저장하고 마지막 글자가 폭발 문자열의 마지막 글자와 일치하다면 한 글자씩 비교하도록 하였습니다.
만약 모든 글자가 같다면 index를 폭발문자열 만큼 뒤로 이동해서 덮어씌우는 방식으로 문자를 입력해갔습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
  public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    String str = br.readLine();
    String word = br.readLine();
    char[] result = new char[str.length()];
    int index = 0;
    int len = word.length();
    boolean chk = false;

    for (int i = 0; i < str.length(); ++i) {
      result[index] = str.charAt(i);
      if (index >= len - 1) {
        for (int j = 0; j < len; ++j) {
          chk = true;
          if (result[index - j] != word.charAt(len - 1 - j)) {
            chk = false;
            break;
          }
        }
        if (chk) {
          index -= len;
        } else {
        }
      } 
      ++index;
    }
    
    if (index == 0) {
      bw.write("FRULA");
    }
    
    for (int i = 0; i < index; ++i) {
      bw.write(result[i]);
    }
    
    bw.close();
  }
}