백준 9935 문자열 폭발 풀이 (feat. JAVA)

반복문을 어떻게 써야만 효율적으로 처리할 수 있을까 고민했던 문제

나중에 알고보니 stack을 써서 뒤에서부터 처리하면 무려 세가지 이점이나 챙겨갈 수 있었다

굉장히 쉽게
누락되지 않고
한번의 반복문으로

 

다른 풀이법들 공부해보니까 그냥 내가 초기에 생각하던대로 반복문으로 진행하는 것이 꽤 많더라

다만 내가 생각했던 것과는 다르게 폭탄의 끝 문자열을 비교하면서 이동하다가 일치하는 순간에 역순으로 탐지해가는 식

 

예를들어

문자열 `aaaaC4aa`가 있고 폭발 문자열이 `C4`이면, 비교 문자열은 항상 `4`이다

문자열은 순차적으로 탐색하다가, 문자열의 `4`와 폭발 문자열의 `4`가 일치하는 순간, 폭발 문자열을 역순으로 탐지해가며 문자열의 `4`이전 문자열과 비교하는 식

이렇게하면 여러 개여도 확실하고 정확하게 삭제할 수 있다

 

다들 이런 방식은 어떻게 생각하는거지.. 더 열심히 풀어봐야겠다

/*
[백준]
9935, 문자열 폭발

[문제파악]
- 상근이는 문자열에 폭발 문자열을 심어 놓았다.
- 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.
- 폭발은 다음과 같은 과정으로 진행된다.
    - 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다.
    - 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
    - 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
    - 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.
    - 상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다.
    - 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.

- 폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

[입력]
- 첫째 줄에 문자열이 주어진다.
- 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.
- 둘째 줄에 폭발 문자열이 주어진다.
- 길이는 1보다 크거나 같고, 36보다 작거나 같다.
- 두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.

[출력]
- 첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.

[구현방법]
- 일단 배열로 하면, 터뜨린 문자열 처리를 별도로 해야하므로 리스트를 사용한다
- 또한, 배열의 가변적 길이를 고려해서 범위를 조절해야함에 유의해야할듯하다
- 당장 생각 나는 것은 반복문을 써서 무식하게 찾는 방법밖에 생각나지 않음
- 예를들어 C4라는 것을 찾을 건데 for문 돌리다가 C를 발견하면 그 다음에 4가 맞는지 체크하는 방식
- 더 효율적인 방법 없으려나.. 근데 2.5초면 될 것 같기도 하다 (문자열 최대 길이가  1,000,000라서..)
- 근데 반복문을 여러번 돌리게 되면 말짱 도루묵이라...
- 효율적인 반복 구조를 생각해야할 것 같다
- 짱구 아무리 굴려봐도 터질 것 같은데.. 싶어서 힌트 보니까 스택을 쓰라네...?
- 폭탄 키워드를 끝단부터 매칭되는 걸 찾아서 확인되면 pop해서 다시 확인하면 될듯하다 (C4가 키워드이면 4 -> C 순으로 확인)
- 이렇게 하면 단 한번의 탐색으로 끝낼 수 있다 끝내주는디..?

[보완점]

*/

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

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

        String words = br.readLine();
        StringBuilder bomb = new StringBuilder(br.readLine()).reverse();
        int bombLength = bomb.length();

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

        for (int i = 0; i < words.length(); i++) {
            char curr = words.charAt(i);

            // 첫번째 비교 키워드가 같고, stack에 비교할만큼의 문자열이 들어있다면
            // bombLength - 1인 이유는 문자열 하나가 curr에 저장되어 있기 때문이다
            if (bombLength - 1 <= stack.size() && curr == bomb.charAt(0)) {
                boolean isDifference = false;

                // stack에서 하나씩 꺼내가며 비교하기
                // 근데 꺼냈는데 중간까지는 맞았다가 그 이후에 틀리면 어떻게 다시 밀어넣지..? 이걸 또 어디에 기억하고 있어야하나.. 뭔가 비효율적인데 하...
                // stack도 .get()을 지원해서 하나씩 다 꺼내볼 필요가 없다;; (get은 index로 작용함)
                for (int j = 1; j < bombLength; j++) {
                    // 비교하는데 하나라도 다르면 break;
                    if (stack.get(stack.size() - j) != bomb.charAt(j)) {
                        isDifference = true;  // 폭탄 키워드 아님
                        stack.push(curr);  // 폭탄 키워드가 아니면 push (이걸 까먹으면 안됨)
                        break;
                    }
                }

                if (!isDifference) {
                    // 다 같다면 이는 폭파 시키면 됨
                    // 반복문 돌려서 bomb 문자열 갯수만큼 pop
                    // 다만 키워드의 맨 마지막 단어를 curr에 저장되어 있는 상태니 반복문의 index인 k는 1부터 시작한다
                    // 12ab이면 b를 현재 curr에 저장되어 있으니 a -> 2 -> 1 순으로 확인해야하니 인덱스 k는 1부터 시작한다는 의미
                    for (int k = 1; k < bombLength; k++) stack.pop();
                }
            } else {
                // 그게 아니면 stack에 넣기
                stack.push(curr);
            }
        }

        // stack이 비어 있으면 더 볼 것 없이 바로 FRULA 출력하고 끝
        if (stack.isEmpty()) sb.append("FRULA");
        else {
            // stack이 비어 있지 않으면 stack에 있는 것들 전부 출력
            for (Character character : stack) {
                sb.append(character);
            }
        }

        System.out.println(sb);
    }
}