문제

백준 9935 문자열 폭발
골드 4

📌 문제 요약

주어진 문자열에서 폭발 문자열(bomb) 이 등장할 때마다 즉시 제거해야 한다.
폭발 문자열이 제거되면 양쪽 문자열이 합쳐지고, 합쳐진 문자열에서도 다시 폭발 문자열이 등장할 수 있다.

모든 폭발이 끝난 후 남은 문자열을 출력하며, 아무 문자도 남지 않으면 "FRULA" 를 출력한다.

📌 폭발 규칙

1. 문자열 안에 폭발 문자열이 포함되어 있으면 모든 폭발 문자열이 한 번에 제거된다.
2. 제거 후 문자열이 이어 붙는다.
3. 이어 붙인 문자열에서도 폭발 문자열이 있을 수 있으며, 없을 때까지 반복한다.
4. 폭발 문자열은 중복 문자를 포함하지 않는다.

---

📌 입력

• 첫째 줄: 문자열 (길이 1 이상 1,000,000 이하)
• 둘째 줄: 폭발 문자열 (길이 1 이상 36 이하)
• 영문 대소문자 + 숫자 0~9

📌 출력

• 모든 폭발 과정을 끝낸 뒤 남은 문자열
• 아무 것도 남지 않으면 "FRULA"

풀이 과정

초기 접근

문제를 보았을 때는 배열이나 리스트에서 넣어서 폭발 문자열이 있는지를 반복해서 순환하는 방법밖에 떠오르지 않았다.
그러나 문자열의 길이가 최대 백만개이기 때문에 배열을 두번만 돌아도 메모리가 터져버릴 것이다.

스택 사용

이 문제를 스택을 이용해서 효율적으로 풀 수 있다.

🔎 StringBuilder를 스택처럼 활용

• 문자를 하나씩 append() 하면서 스택처럼 쌓는다.
• 방금 넣은 문자가 폭발 문자열의 마지막 문자와 같다면,
• 스택의 뒤쪽 substring이 폭발 문자열과 같은지 비교한다.
• 같다면 → 그 부분을 delete()로 제거한다.
• 이 과정은 O(폭발 문자열 길이)만큼만 검사하면 되므로 매우 효율적이다.

즉, 문자열 전체를 매번 확인할 필요가 없고,
"스택 뒤에서 필요한 만큼만 확인" 하면 되므로 시간 복잡도는 사실상 O(N)에 가깝다.

구현 상세

자바에는 스택 클래스가 있지만 오래되어 효율성이 낮아도 한다.
해당 문제는 문자열이기 때문에 StringBuilder를 스택처럼 사용할 수 있다.

1) 문자를 하나씩 StringBuilder에 추가

		StringBuilder sb = new StringBuilder();

		for (int i = 0 ; i < string.length();i ++) {
			//한 글자씩 넣기 

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

2) 폭발 가능성 체크

• 현재 추가한 문자 == 폭발 문자열의 마지막 문자
• 현재 sb 길이 ≥ 폭발 문자열 길이

이 조건이 만족되면 실제로 폭발 문자열인지 확인한다.

			//지금 넣는 수가 타겟의 마지막과 같다면...
			if (string.charAt(i) == target.charAt(target.length() - 1) && sb.length() >= target.length()) {
				boolean match = true;
				for (int j = 0 ; j < target.length(); j++) {
					if (sb.charAt(sb.length() -1 - j) != target.charAt(target.length() - 1 - j)) {
						match = false;
						break;
					}
				}
				//만약에 문자열이 같다면 폭발 진
				if (match) {
					sb.delete(sb.length() - target.length(), sb.length());
				}
			}
		}

3) 최종 출력

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

전체코드

package Algorithm;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class backjoon_문자열폭발 {
	public static void main(String[] args) throws FileNotFoundException {
		// 입력값 받기
		System.setIn(new FileInputStream("src/input.txt"));

		Scanner sc = new Scanner(System.in);

		String string = sc.next();

		String target = sc.next();

		StringBuilder sb = new StringBuilder();

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

			// 한 글자씩 넣기
			sb.append(string.charAt(i));
			System.out.println("추가 후 : " + sb);

			// 지금 넣는 수가 타겟의 마지막과 같다면...
			if (string.charAt(i) == target.charAt(target.length() - 1) && sb.length() >= target.length()) {
				boolean match = true;
				for (int j = 0; j < target.length(); j++) {
					if (sb.charAt(sb.length() - 1 - j) != target.charAt(target.length() - 1 - j)) {
						match = false;
						break;
					}
				}
				// 만약에 문자열이 같다면 폭발 진
				if (match) {
					sb.delete(sb.length() - target.length(), sb.length());
				}
			}
		}
		if (sb.length() == 0) {
			System.out.println("FRULA");
		} else {
			System.out.println(sb);
		}

	}
}