백준 9935번 : 문자열 폭발(Java)

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

9935번: 문자열 폭발

---

[풀이]

 

 replace를 사용해서 메소드를 푸니 메모리 초과로 문제를 풀지 못했다. 찾아보니 나 이외에도 replace를 사용해서 메모리 초과를 겪으신 분들이 많았다. ㅎㅎ 그래서 다음에 시도한 방식은 스택을 이용해서 푸는 방식이다! 폭탄의 문자열 길이만큼 기존의 입력 문자열과 비교해서(이때, boolean 변수를 하나 이용했다.) 풀이를 진행했다. 

 

 이 과정에서 stack.get(index)의 index를 구하는 부분에서 시간이 좀 걸렸으며 추후, 다시 한번 풀어봐야할 문제라고 생각한다!

 

---

[코드]

 

1. replace 사용한 풀이 코드

 

public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        String input = reader.readLine();
        String bomb = reader.readLine();
        String answer = "";

        while(true){
            if(input.length() == 0){
                answer = "FRULA";
                break;
            }
            if(input.contains(bomb)){
                input = input.replace(bomb,"");
            }else{
                answer = input;
                break;
            }
        }
        System.out.println(answer);
    }

 

2. 스택을 이용한 풀이 코드

 

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

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

        String input = reader.readLine();
        String bomb = reader.readLine();
        StringBuilder sb = new StringBuilder();

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

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

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

                if (flag == true) {
                    for (int k = 0; k < bomb.length(); k++) {
                        stack.pop();
                    }
                }
            }
        }

        for (Character c : stack) {
            sb.append(c);
        }

        if (sb.length() == 0) {
            System.out.println("FRULA");
        } else {
            System.out.println(sb.toString());
        }
    }
}