백준 9935번 (java)

백준 9935 문자열 폭발 java

관찰

스택을 이용해서 문자열이 같은지 확인하고 같으면 터트려서 스택 관리를 해주면 될 거 같다! 주의해야 할 점은 확인하는 문자열 마지막과 비교해서 계속해서 터트려줘야 한다!

정답코드

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

public class Main {
    static char[] origin;
    static char[] bomb;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        origin = br.readLine().toCharArray();
        bomb = br.readLine().toCharArray();
        int bombIdx = bomb.length - 1;
        ArrayDeque<Character> deque = new ArrayDeque<Character>();

        for(int i=0;i<origin.length;i++){
            deque.addLast(origin[i]);
            // bomb 글자 마지막과 비교해서 같으면 탐색 시작!
            if(deque.getLast() == bomb[bombIdx] && deque.size() > bombIdx){
                char[] tmp = new char[bombIdx+1];
                for (int j = bombIdx; j >= 0; j--) {
                    tmp[j] = deque.pollLast();
                }
                // 다른 부분이 있다면 flag = 1;
                int flag = 0;
                for(int j=0;j<=bombIdx;j++){
                    if(tmp[j] != bomb[j]) flag = 1;
                }
                // 만약 틀리다면 원상복구
                if(flag == 1) {
                    for(int j=0;j<=bombIdx;j++){
                        deque.addLast(tmp[j]);
                    }
                }
                // flag == 0이면 pop한 상태 그대로
            }
        }
        if(deque.isEmpty()){
            System.out.println("FRULA");
        }
        else{
            while(!deque.isEmpty()){
                sb.append(deque.removeFirst());
            }
            System.out.println(sb.toString());
        }
    }
}

느낀점

사실 문제를 보자마자 너무 스택 문제여서 바로 풀었지만 시간초과가 계속 떠서 30분을 더 고민했다.. 정답 코드처럼 ArrayDeque으로도 바꿔보고 배열로 생구현도 하면서 시간을 날리다가 결국 StringBuilder 를 쓰니 더럽게 풀어도 통과가 됐다.. 내 30분...