[백준] 9935 - 문자열 폭발

[문제링크]

9935번: 문자열 폭발

 

0. 폭탄 진행현황을 index로 검사한다

 

1. 현재 index에 맞는 문자가 들어오면 : 누적 후 index+1

 

2. 현재 index와 다른 문자가 들어오면

  - 폭탄의 첫 문자이다 : 새 폭탄의 시작점일 가능성, 현재 index정보를 백업하고 누적, index=1부터 다시 시작

  - 일반 문자이다 : 폭탄이 아니므로 모든 index를 제거, 누적된 문자들을 출력 문자열에 추가하고 index=0

  - 폭탄의 마지막 문자이다 : 폭탄이 터진다. 누적한 문자를 제거하고 백업한 index복구, 없으면 index=0

 

3. 모든 문자를 순회 후 : 누적한 문자가 있다면 출력 문자열에 추가

 

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringBuilder sb2;
		
		String s = br.readLine();
		String boom = br.readLine();
		
		int idx=0;
		Stack<Character> charStack = new Stack<>();
		Stack<Integer> idxStack = new Stack<>();
		
		for (int i = 0; i < s.length(); i++) {
			char cur = s.charAt(i);
			
			if(cur==boom.charAt(idx)) {
				//폭탄이 순조롭게 진행중
				idx++;
				charStack.add(cur);
				if(idx == boom.length()) {
					//폭탄의 완성
					//charStack에서 완성한 boom 비우기
					
					for (int j = 0; j < idx; j++) {
						charStack.pop();
					}
					//idx가 존재한다면, 복구하기
					if(!idxStack.isEmpty()) {
						idx = idxStack.pop();
					}else {
						idx = 0;
					}
				}
			}
			else {
				if(cur==boom.charAt(0)) {
					//새 폭탄의 시작
					idxStack.add(idx);
					charStack.add(cur);
					idx=1;
				}
				else {
					//평범한 문자열일 경우
					//쌓은 idx 다비우고
					idxStack.clear();
					
					//쌓인 char들은 boom이 아니므로 다 넣는다
					sb2 = new StringBuilder();
					while(!charStack.isEmpty()) {
						sb2.append(charStack.pop());
					}sb.append(sb2.reverse());
					//마지막에 현재 문자 반영
					sb.append(cur);
					idx=0;
				}
			}
		}
		sb2 = new StringBuilder();
		while(!charStack.isEmpty()) {
			sb2.append(charStack.pop());
		}sb.append(sb2.reverse());
		if("".equals(sb.toString())) System.out.println("FRULA");
		else System.out.println(sb);
        
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면