[백준] 9935 문자열 폭발

1. 문제

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

9935번: 문자열 폭발

2. 접근방법

스택으로 left, right 를 두고

중간에 문자열 검사용 StringBuilder를 하나 둬서 풀이했다.

left - StringBuilder - right

stack이 아닌 전체 문자열로 삭제 추가를 하면 O(N)이 들어서 시간초과가 나게 된다.

 

1. 먼저 right에 최초 문자를 reverse로 집어 넣어둔다.

2. right에서 하나씩 꺼내서 폭발문자열과 같으면 sb에 넣는다.

3. 다음 문자도 꺼내서 다음 폭발 문자열과 비교한다.

4. 이렇게 모든 문자열과 같으면 sb에 있던 값을 초기화 하고

문자열이 변경되었기 때문에 다시 검사를 진행하도록 폭발 문자열 길이 만큼 left에서 꺼내 right에 넣는다.

5. 만약 검사 중간에 달라질 경우 sb에 있던 값을 left에 다 집어넣고 현재 검사 중이던 값은 0번 인덱스와 비교할 수 있게 해준다.

6. 모든 과정이 끝나고 sb에 남은 문자열을 left에 넣고 left에 값을 하나씩 꺼내 하나의 string으로 만든 뒤 reverse하여 출력 

 

3. 자바 코드

package backjoon;

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

public class P9935문자열폭발 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String target = br.readLine();
        String bomb = br.readLine();
        String result = boom(target,bomb);
        System.out.println(result);
    }

    static String boom(String target,String bomb) {
        Stack<Character> left = new Stack<>();
        Stack<Character> right = new Stack<>();
        for(int i = target.length()-1  ; i >= 0 ; i-- ){
            right.push(target.charAt(i));
        }
        StringBuilder sb = new StringBuilder();
        int bombIdx = 0;
        while(!right.isEmpty()){
            char now = right.pop();
            if(now == bomb.charAt(bombIdx)){
                sb.append(now);
                bombIdx = bombIdx+1;
                if(bombIdx == bomb.length()){
                    sb = new StringBuilder();
                    bombIdx = 0;
                    for(int i = 0 ; i < bomb.length() -1 ; i++){
                        if(left.isEmpty()) break;
                        right.push(left.pop());
                    }
                }
            }else{
                for(int i = 0 ; i < sb.length() ; i++) left.push(sb.charAt(i));
                if(sb.length() != 0)right.push(now);
                else left.push(now);
                sb = new StringBuilder();
                bombIdx = 0;
            }
        }
        for(int i = 0 ; i < sb.length() ; i++) left.push(sb.charAt(i));
        StringBuilder result = new StringBuilder();
        while(!left.isEmpty()) result.append(left.pop());
        return result.length() == 0 ? "FRULA" : result.reverse().toString();
    }
}

4. 마치며

1년 6개월 전에 문자열 삭제로 풀고 시간초과 뜨게 풀었었는데, 왜 그랬니 ..?