[백준 java] 9935 - 문자열 폭발

 

진짜 폭발시키고 싶은 문제

 

String replace를 사용하면 O(N^2) 번의 시간복잡도가 발생하므로 Stack을 사용하는 방법으로 풀어야한다.

(문자열 탐색후 지우고 다시 처음부터 탐색하기 때문)

폭발 문자열 = B

1. 입력값을 char[]로 받은 후 스택에 처음부터 하나씩 넣는다

2. 만약 스택 사이즈가 B보다 크다면

3. 스택에 넣은 값에 B의 길이만큼 뺀 값과 B를 한글자씩 for문으로 비교한다

4. 만약 explosion = true 라면 B의 길이만큼 스택에서 버린다. (선입선출)

 

계산 후 for문을 사용하여 값을 출력했는데 여기서 또 시간초과가 발생했다

for문을 사용하여 출력할때도 O(N^2) 번의 시간복잡도가 발생해서 그렇다

시간 복잡도, 입출력

위 글을 참고하여 StringBuilder로 입출력을 구현하였다.

적어도 한 4번이상은 제출하고 틀린 것 같다

 

 

import java.util.*;

// 문자열 폭발
// https://www.acmicpc.net/problem/9935
public class B9935 {

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

        char[] chArr = sc.next().toCharArray();
        char[] Bomb =  sc.next().toCharArray();

        Stack<Character> stack = new Stack<>();
        for (char c : chArr) {
            stack.push(c);
            if (stack.size() >= Bomb.length) {
                boolean explosion = true;
                for (int j = 0; j < Bomb.length; j++) {
                    if (stack.get(stack.size() - Bomb.length + j) != Bomb[j]) {
                        explosion = false;
                        break;
                    }
                }
                if (explosion) {
                    for (int j = 0; j < Bomb.length; j++) {
                        stack.pop();
                    }
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for (Character character : stack) {
            sb.append(character);
        }
        if(sb.toString().length()==0) System.out.println("FRULA");
        else System.out.println(sb.toString());
    }
}