[BaekJoon] 9935 문자열 폭발

1.  문제 링크

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

2.  문제

요약

• 문자열에 폭발 문자열이 심어져있고 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 됩니다.
• 폭발은 다음과 같은 과정으로 진행됩니다.
  • 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 됩니다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만듭니다.
  • 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있습니다.
  • 폭발은 폭발 문자열이 문자열에 없을 때까지 계속됩니다.
• 문자열과 폭발 문자열이 주어졌을 때, 모든 폭발이 끝난 후에 어떤 문자열이 남아있는지 구하는 문제입니다.
• 입력: 첫 번째 줄에 길이가 1보다 크거나 같고 1,000,000보다 작거나 같은 문자열이 주어지고 두 번째 줄에 길이가 1보다 크거나 같고 36보다 작거나 같은 폭발 문자열이 주어집니다.
  • 두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있습니다.
• 출력: 첫 번째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력합니다. 남아있는 문자가 없다면 "FRULA"를 출력합니다.

3.  소스코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static String str, explosion;
	static void input() {
		Reader scanner = new Reader();
		str = scanner.nextLine();
		explosion = scanner.nextLine();
	}
	
	static void solution() {
		Stack<Character> strStack = new Stack<Character>();
		for(int index = 0; index < str.length(); index++) {
			strStack.push(str.charAt(index));
			if(strStack.size() >= explosion.length()) {
				boolean flag = true;
				for(int index2 = 0; index2 < explosion.length(); index2++) {
					if(strStack.get(strStack.size() - explosion.length() + index2) != explosion.charAt(index2)) {
						flag = false;
						break;
					}
				}
				if(flag) {
					for(int index2 = 0; index2 < explosion.length(); index2++)
						strStack.pop();
				}
			}
		}
		for(Character c : strStack) sb.append(c);
		if(sb.length() == 0) System.out.println("FRULA");
		else System.out.println(sb);
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch(IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}
}

4.  접근

• 수열의 각 수들을 탐색하면서 현재 수열의 수가 이전의 수열의 수보다 작으면 Stack에 현재 수열의 수에 해당하는 index를 넣습니다.
• 그러다 만약 현재 수열의 수가 Stack에서 꺼낸 수를 index로 하는 수열의 수보다 크다면 Stack의 원소를 꺼내서 삭제하고 Stack에서 꺼낸 수를 index로 하는 수열의 수를 현재 수열의 수로 변경합니다.
• 모든 수열의 수에 대해 탐색하였는데 아직 Stack에 수가 남아있다면 이 수들은 자신보다 큰 수를 자신의 오른쪽에서 만나지 못했다는 뜻이므로 Stack에 남아있는 수들을 index로 하는 수열의 수를 -1로 변경합니다.