[백준 - 9935] 골드4 - 문자열 폭발

www.acmicpc.net/problem/9935

9935번: 문자열 폭발

 

1. 유형

stack, 문자열

 

2. 풀이법

 

12ab112ab2ab

12ab

 

이 값이 입력값으로 주어진다면, 폭탄의 마지막 문자가 b 니깐, b를 만났을때만 폭탄 길이만큼

 

앞을 탐색해 주는 식으로 풀었다.

 

그럼에도 불구하고, 계속 시간초과가 났는데 StringBuilder를 쓰니깐 해결되었다.

 

3. 코드

package 문자열;

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

public class back_9935문자열폭발 {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		Stack<Character> stack = new Stack<>();  
		String str = in.readLine();
		String bom = in.readLine();
		int bomLen = bom.length();
		char lastChar = bom.charAt(bom.length()-1);
		//총 길이 탐색하기
		for(int i=0; i < str.length(); i++) {
		//끝 문자열 탐색
			stack.push(str.charAt(i));
			if(stack.peek()==lastChar && stack.size()>=bomLen) {
				ArrayList<Character> list = new ArrayList<>();
				boolean flag = true;
				for(int j=bomLen-1; j>=0; j--) {
					list.add(stack.peek());
					if(stack.pop() != bom.charAt(j)) {
						flag = false;
						break;
					}
				}
				if(!flag) {
					Collections.reverse(list);
					stack.addAll(list);
				}
			}
		}
		ArrayList<Character> list = new ArrayList<>();
		if(stack.size()!=0) {
			//거꾸로 출력
			while(!stack.empty()) {
				list.add(stack.pop());
			}
			for(int i=list.size()-1; i>=0; i--) {
				sb.append(list.get(i));
			}
			System.out.println(sb.toString());
		}else {
			//실패 출력
			System.out.println("FRULA");
		}
	}
}