[Java] BOJ 9935 문자열 폭발

[Java] BOJ 9935 문자열 폭발

 

www.acmicpc.net/problem/9935

9935번: 문자열 폭발

 

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class BOJ_9935_문자열폭발 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader((System.in)));
		String s = br.readLine();
		String bomb = br.readLine();
		int bombLen = bomb.length();
		
		char[] ans = new char[s.length()];
		int ansIdx = 0;
		for (int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			ans[ansIdx++] = c;
			if(c != bomb.charAt(bombLen-1)) continue;
			boolean isSame = true;
			int idx = ansIdx-2;
			for (int j = bombLen-2; j >= 0; j--) {
				if(idx < 0) {
					isSame = false;
					break;
				}
				if(ans[idx--] != bomb.charAt(j)) {
					isSame = false;
					break;
				}
			}
			if(isSame) {
				ansIdx -= bombLen;
			}
		}
		
		if(ansIdx == 0)	System.out.println("FRULA");
		else System.out.println(String.valueOf(ans, 0, ansIdx));
		
	} // main
}

 

처음에 stringbuilder indexOf 로 했다가 시간초과가 너무 많이 나서

string replaceAll 로 했는데도 시간초과가 계속 나서

결국 다른 사람의 코드를 참고했다...

 

char[] 배열에 받은 문자열을 한 문자씩 넣다가 폭발 문자열 마지막 글자와 같은 것을 발견하면 그 글자부터 거꾸로 폭발 문자열이 맞는 지 검사한다.

폭발 문자열이 맞다면 char[] 배열 인덱스를 폭발 문자열 길이만큼 줄여서 덮어쓴다.! (이 부분이 매우 똑똑한 듯)

 

혹은

 

폭발 문자열이 아니라면 그냥 계속 char[] 배열에 문자를 하나씩 넣는다.

 

받은 문자열을 끝까지 순회했다면 종료하고

 

char 배열의 길이가 0이면 FRULA

아니면 String.valueOf(char[], 시작인덱스, 끝인덱스) 로 char 배열을 출력한다.

(그냥 char 순회하며 출력하면 또 시간초과 난다...)

 

String.valueOf 는 문자열배열을 순회하지 않고 바로 문자열로 변환해주는 함수다.