[백준]9935_문자열폭발_Stack

[문제 링크]

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

9935번: 문자열 폭발

 

[생각 흐름]

처음에는 자바에서 제공하는 replace를 반복하려 했으나 시간 초과 문제가 있다고 하여 스택으로 변경하였다

폭발하는 문자열의 마지막 문자열의 마지막 문자를 저장해 두고 그것과 같은 문자가 들어오는 경우 스택을 확인하는 방식으로 알고리즘을 

구현하였다 

푸는 중 2%에서 계속 메모리 초과 오류가 발생했는데 StringBuilder 클래스를 사용하여 마지막 스택에 있는 문자를 모두 출력하니까

문제가 해결되었다. 

 

[코드]

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();

        Stack<Character> s = new Stack<>();

        String bomb = br.readLine();

        int bomblen = bomb.length();
        char last = bomb.charAt(bomblen-1);

        for(int i=0;i<input.length();i++){
            char c = input.charAt(i);
            s.push(c);

            if(c==last && bomblen<=s.size()){
                boolean f = true;
                for(int j=0;j<bomblen;j++){
                    if(s.get(s.size()-j-1)== bomb.charAt(bomblen-j-1))continue;
                    else {
                        f=false;
                        break;
                    }
                }
                if(f){
                    for(int j=0;j<bomblen;j++) s.pop();
                }
            }
            //System.out.println(Arrays.toString(s.toArray()));
        }

        StringBuilder ans= new StringBuilder();
        for(Character c : s){
            ans.append(c);
        }
        ans = (ans.length()==0)?ans.append("FRULA"):ans;
        System.out.println(ans);

    }
}