[Algorithm] 🤯백준 9935 문자열 폭발

0. 문제

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

• 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
• 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
• 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.
  
  상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.
  
  폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

입력
첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.

두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.

출력
첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.

1. 아이디어

💡 스택 사용
💡 stack에 문자열을 하나씩 넣음
💡 stack 크기가 bomb크기와 같거나 커지면, bomb사이즈만큼 stack에서 가져와서 bomb와 같은 지 파악함
💡 stack에서 빼온 문자열이 bomb와 같다면, stack에서 제거함
💡 stack의 크기가 0이면 FRULA 아니라면 stack에 있는 문자열을 출력함

2. 핵심 풀이

1. stack에 문자열을 하나씩 넣음

s.push(str[i]);

2. stack 크기가 bomb크기와 같거나 커지면, bomb사이즈만큼 stack에서 가져와서 bomb와 같은 지 파악함

if(s.size() >= len) {
	boolean flag =true;
				
	int tmp = s.size()-len;
				
	for(int j=0; j<len; j++) {
		if(s.get(tmp+j) != bomb.charAt(j)) {
			flag = false;
			break;
		}
	}
}

3. stack에서 빼온 문자열이 bomb와 같다면, stack에서 제거함

if(flag) {
	for(int j=0; j<len; j++) {
		s.pop();
	}
}

4. stack의 크기가 0이면 FRULA 아니라면 stack에 있는 문자열을 출력함

bw.write(sb.length() > 0 ? sb.toString() : "FRULA");

3. 코드

import java.io.BufferedWriter;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;

public class BOJ_9935 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		char[] str = br.readLine().toCharArray();
		String bomb = br.readLine();
		Stack<Character> s = new Stack<Character>();
		int len = bomb.length();
		
		for(int i=0; i<str.length; i++) {
			s.push(str[i]);
			
			if(s.size() >= len) {
				boolean flag =true;
				
				int tmp = s.size()-len;
				
				for(int j=0; j<len; j++) {
					if(s.get(tmp+j) != bomb.charAt(j)) {
						flag = false;
						break;
					}
				}
				
				if(flag) {
					for(int j=0; j<len; j++) {
						s.pop();
					}
				}
			}
		}
		
		for(char c : s) {
			sb.append(c);
		}
		
		bw.write(sb.length() > 0 ? sb.toString() : "FRULA");
		bw.flush();
		bw.close();
		
	}

}

4. 결과

성공✨