[알고리즘]백준 9935: 문자열 폭발

 

해결 방법

먼저, 전체 문자열에서 폭발 문자열을 찾고 다시 문자열을 이어붙여 탐색하는 풀이가 떠오른다. 최악의 경우 전체 문자열의 길이가 N, 폭발 문자열의 길이가 1d일때, N*(N-1)(N-2)…*1의 연산이 필요하다. 즉, O(N^2)이 되어 시간초과가 발생할 것이다. 그래서 스택을 사용해서 O(N)으로 문제를 해결해야 한다.

 

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        int SIZE = str.length();
        String bomb = br.readLine();
        int bombSize = bomb.length();

        Stack<Character> stack = new Stack<>();
        for(int i=0; i<SIZE; i++){
            stack.add(str.charAt(i));

            if(stack.size()>=bombSize){
                boolean isBomb = true;

                for(int j=0; j<bombSize; j++){
                    if(stack.get(stack.size()-bombSize+j)!=bomb.charAt(j)){
                        isBomb = false;
                        break;
                    }
                }

                if(isBomb){
                    for(int j=0; j<bombSize; j++) stack.pop();
                }
            }
        }

        if(stack.size()==0) System.out.println("FRULA");
        else{
            StringBuilder sb = new StringBuilder();
            for(int i=0; i<stack.size(); i++) sb.append(stack.get(i));
            System.out.println(sb);
        }
    }
}

 

링크

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