백준 9935 : 문자열 폭발

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

9935번: 문자열 폭발

[ 문제풀이 ]

주어진 문자열의 길이가 최대 1000000이기 때문에 문자열에서 폭발 문자열이 존재하지 않을 때까지 탐색 후 제거하는 방법으로는 TLE가 발생하게 된다.

해당 문제는 한번의 탐색으로 탐색 및 제거를 처리해줘야 하는데 이는 스택 자료구조를 활용하면 해결할 수 있다.

문자열을 처음부터 탐색하다가 폭발 문자열의 마지막 문자를 만나게되면 스택의 Top부터 역으로 폭발 문자열의 길이만큼 비교해주면서 일치하다면 제거해주면 된다.

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

public class Main {

	public static void main(String[] args) throws IOException {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))){
			String input = br.readLine();
			String bomb = br.readLine();
			Stack<Character> st = new Stack<>();
			
			for (int i = 0; i < input.length(); ++i) {
				st.push(input.charAt(i));
				
				if (st.peek() == bomb.charAt(bomb.length() - 1) && st.size() >= bomb.length()) {
					boolean flag = true;
					for (int j = 1; j <= bomb.length(); ++j) {
						if (st.get(st.size() - j) != bomb.charAt(bomb.length() - j)) {
							flag = false;
							break;
						}
					}
					
					if (flag) {
						for (int j = 0; j < bomb.length(); ++j) {
							st.pop();
						}
					}
				}
			}
			
			if (st.isEmpty()) bw.write("FRULA");
			else {
				for (int i = 0; i < st.size(); ++i) {
					bw.write(st.get(i));
				}
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}