문자열 폭발

📍 문제 설명

 

💡 접근

문자열의 최대 길이는 100만이므로 replaceAll 메서드를 사용하거나 문자 제거 해준후 다시 전체 문자열에 대해서 탐색할 때 시간초과 판정이 난다.

1.문자를 스택에 push 한다.

2.스택의 길이가 폭발 문자열의 길이보다 같거나 클 때 폭발 문자열인지 확인한다.

3.폭발 문자열과 일치하면 폭발 문자열만큼 스택에서 pop 한다.

4.남은 문자열을 출력한다.

 

👩‍💻 코드

import java.util.*;

public class Main {
    static long n, m, k, cnt, max, min, sum, count, r, c, result, answer = Integer.MAX_VALUE;
    static char[][] board, clone, dis;
    static boolean[][] visited;
    static String str,explosionStr;
    static int explosionLength;
    static int[] ch, pm, combi, graph, temp;
    static boolean flag = false;
    static int[] dx = {-1, 0, 1, 0,}; //북동남서
    static int[] dy = {0, 1, 0, -1};
    static ArrayList<Integer> list = new ArrayList<>();

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);

        str = kb.nextLine();
        explosionStr = kb.nextLine();
        explosionLength = explosionStr.length();
        T.solution();
    }
    
    private void solution() {
        Stack<Character> s = new Stack<>();
        for(int i = 0; i < str.length(); i++) {
            s.push(str.charAt(i));

            //폭발 문자열과 길이가 같거나 클때 폭발 문자열인지 확인
            if(s.size() >= explosionLength) {
                boolean flag = true;
                //다른 부분이 있으면 멈춘다.
                for(int j = 0; j < explosionLength; j++) {
                    if(s.get(s.size()-explosionLength+j) != explosionStr.charAt(j)) {
                        flag = false;
                        break;
                    }
                }
                //폭발 문자열과 일치하면 그만큼 pop 시켜준다.
                if(flag) for(int j = 0; j < explosionLength; j++) s.pop();
            }
        }
        StringBuffer sb = new StringBuffer();
        for(char c : s) sb.append(c);
        System.out.println(sb.length() == 0 ? "FRULA" : sb.toString());
    }
}