[Algorithm/BOJ] 자바 - 문자열 폭발(9935)

문제	플랫폼	난이도	유형	풀이 링크	문제 링크
문자열 폭발(9935)	BOJ	Gold 4	String, Stack	풀이	문제

풀이

1. 문자열에 폭발 문자열이 존재할 경우 해당 폭발 문자열을 삭제합니다.
2. 남은 문자열에 폭발 문자열이 있는 지 확인하며 없을 때까지 반복합니다.
3. 문자열에 폭발 문자열이 없을 경우 남은 문자열을 출력합니다. 이 때, 남은 문자열이 없다면 "FRULA"를 출력합니다.

과정은 다음와 같이 일치하는 문자열을 삭제하면서,
일치하는 문자열이 없을 때까지 반복하면 됩니다.

Case 1 : 구현

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    String str = br.readLine(); // 주어진 문자열
    String bombStr = br.readLine(); // 폭발 문자열
    int bombLen = bombStr.length();

    StringBuilder sb = new StringBuilder();
    int sbSize = 0;

    for (int i = 0; i < str.length(); i++) {
        if (sbSize - bombLen < 0) {
            sb.append(str.substring(i, i + 1));
            sbSize += 1;
            continue;
        }

        if (sb.substring(sbSize - bombLen, sbSize).equals(bombStr)) {
            sb.delete(sbSize - bombLen, sbSize);
            sbSize -= bombLen;
        }

        sb.append(str.substring(i, i + 1));
        sbSize += 1;
    }

    if (sb.substring(sbSize - bombLen, sbSize).equals(bombStr)) {
        sb.delete(sbSize - bombLen, sbSize);
    }

    if (sb.length() == 0)
        System.out.println("FRULA");
    else
        System.out.println(sb.toString());

}

Case 2 :

public class 문자열폭발_V2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String input = br.readLine();
        String bomb = br.readLine();

        String ans = explosion(input, bomb);
        System.out.println(ans.length() == 0 ? "FRULA" : ans);
    }

    private static String explosion(String input, String bomb) {
        char[] result = new char[input.length()];
        int index = 0;

        for (int i = 0; i < input.length(); i++) {
            result[index] = input.charAt(i);

            if (isBomb(result, index, bomb)) {
                index -= bomb.length();
            }

            index += 1;
        }

        return String.valueOf(result, 0, index);
    }

    private static boolean isBomb(char[] result, int index, String bomb) {
        if (index < bomb.length() - 1) {
            return false;
        }

        for (int i = 0; i < bomb.length(); i++) {
            if (bomb.charAt(i) != result[index - bomb.length() + 1 + i]) {
                return false;
            }
        }

        return true;
    }
}

삭제연산 없이, 인덱스를 바탕으로 풀어낸 코드입니다.
explosion()에서 char[] result에 인덱스만 바꾸어 가며 폭발이 일어날 시, 해당 폭발 문자열의 길이만큼 인덱스를 뺀 뒤, 다시 char[] result 해당 인덱스 부분에 새로운 문자열을 덮어쓰면서 반복합니다.

삭제 후 char[] result에 문자는 남아있겠지만, 폭발로 인해 남은 문자열이 없을 때,
return String.valueOf(result, 0, index); 에서 0 ~ 0이므로 결국 빈 문자열을 리턴합니다.