백준 9935 "문자열 폭발" (JAVA)

🔍 문제링크

https://www.acmicpc.net/problem/9935

---

📌 문제 요약

• 문자열 S에서 특정 폭발 문자열 B가 연속으로 등장하면 제거.
• 제거 후 남은 문자열을 다시 검사하여 반복적으로 폭발.
• 최종적으로 남은 문자열이 없다면 "FRULA" 출력.

---

🛠 풀이 및 알고리즘

1. 문자 하나씩 StringBuilder에 추가
   • 폭발 문자열이 형성될 경우 즉시 삭제.
   • 뒤에서 bombStr.length() 만큼 검사하여 폭발 문자열이 있으면 제거.
2. 시간 최적화
   • String을 사용하면 O(N^2) 이상의 복잡도가 발생할 수 있으므로, StringBuilder를 활용하여 문자열 수정 최적화 (O(N)).

---

💡 코드

public class Baekjoon_9935 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String str = sc.next();
        String bombStr = sc.next();
        int len = bombStr.length();
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < str.length(); i++) {

            sb.append(str.charAt(i));

            // 폭탄 문자열이 현재 넣는 문자열 기준으로 같으면 삭제
            if (sb.length() >= len && sb.substring(sb.length() - len).equals(bombStr)) {
                sb.delete(sb.length() - len, sb.length());
            }
        }
        System.out.println(sb.isEmpty() ? "FRULA" : sb.toString());
    }

}

---

🏆 시간 복잡도 분석

• 문자열을 한 번 순회 (O(N)).
• 폭발 문자열 체크 시 substring()을 사용하므로 O(1).
• 최종 시간 복잡도 O(N) + O(1) = O(N)