9935번) 문자열 폭발

문제 출처 : https://www.acmicpc.net/problem/9935

import java.util.Scanner; public class Q9935 { static char[] chars; static String boom; public static void main(String[] args) { Scanner sc = new Scanner(System.in); String string = sc.nextLine(); boom = sc.nextLine(); chars = new char[string.length()]; char lastChar = boom.charAt(boom.length()-1); int nowPoint = 0; for ( int i = 0; i < string.length(); i++ ) { char temp = string.charAt(i); chars[nowPoint] = temp; if ( nowPoint >= boom.length()-1 && temp == lastChar ) { nowPoint = calLast(nowPoint); } else { chars[nowPoint++] = string.charAt(i); } } if ( nowPoint == 0 ) { System.out.println("FRULA"); } else { System.out.println(String.valueOf(chars).substring(0, nowPoint)); } } public static int calLast(int last) { for ( int i = 1; i < boom.length(); i++ ) { if ( boom.charAt(boom.length()-1-i) != chars[last - i] ) { return ++last; } } return last - (boom.length() - 1); } }

char을 하나씩 넣다가, 폭발하는 문자열 마지막 문자와 삽입한 문자가 같을 경우

뒤에서부터 문자열 폭발 검사를 통해 문자열 폭발시킵니다.

이걸 반복하면 폭발할 문자열은 모두 폭발합니다.

그냥 간단히 replace를 하니 시간초과가 뜨네요.