문자열 폭발 - 문자열

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

9935번: 문자열 폭발

[문제요약]

• 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
• 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
• 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.
• 모든 폭발이 끝난 후에 남는 문자열을 구해야 한다.

 

[문제풀이]

일단은 문자열을 나누어서 폭탄 문자열을 확인하며 없애는 식으로 구현했었습니다. 하지만 이렇게 짜게되면 문제의 메모리 제한에 의해 결과가 메모리 초과가 발생하게 됩니다.

 

따라서 스택을 쓰기로 했습니다. 스택을 사용하는 이유로는 일단 입력을 받다가, 폭탄 문자열과 같은지 비교하기 위함인데요. 같을 경우에 빠르게 동일 문자열을 삭제하기 위함입니다.

 

이렇게 했을때 메모리 초과가 안나는 이유로는 java의 string 특성상 불변의 성질을 가지고 있으므로 삭제될 때 새로운 객체를 만들어내는 것이 메모리 초과가 되었던 이유인데요. 제가 구현한 방법은 문자열안에서 삭제하는 것이 아닌 스택에서 하나씩 받아서 삭제를 진행하기 때문에 새롭게 객체가 생기지 않습니다. 따라서 메모리 초과가 발생하지 않는 것입니다.

 

꼭 스택으로만 풀지 않아도 괜찮습니다. String Builder를 사용해도 string처럼 새로운 객첼을 생성하는 것이 아닌 기존의 데이터에 더하는 방식을 사용하기 때문입니다.

 

[코드]

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

public class 문자열_폭발 {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {

        String str = br.readLine();
        String bomb = br.readLine();

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

        for (int i = 0; i < str.length(); i++) {
            stack.push(str.charAt(i));

            if (stack.size() >= bomb.length()) {
                boolean isSame = true;
                for (int j = 0; j < bomb.length(); j++) {
                    if (stack.get(stack.size() - bomb.length() + j) != bomb.charAt(j)) {
                        isSame = false;
                        break;
                    }
                }

                if (isSame) {
                    for (int j = 0; j < bomb.length(); j++) {
                        stack.pop();
                    }
                }
            }
        }
        for (char ch : stack) {
            sb.append(ch);
        }

        System.out.println(sb.length() > 0 ? sb.toString() : "FRULA");
    }
}