문제 9935

풀이 접근

1. 문자열에서 bomb가 존재하면 지우고, 나머지 문자들을 이어서 반환하는 문제이다.

2. 반환된 문자에 또 bomb이 존재한다면 다시 지워 줘야한다.

3. 그래서 풀이 방식을 stack과 재귀 2가지 방식으로 풀었다.

   1. 재귀 (메모리 초과)

      1. input에 bomb가 존재하지 않는다면 input값을 저장하고 return한다.
      2. 만약 input == bomb라면 남아있는 부분이 없기 때문에 FRULA를 저장하고 return한다.
      3. 2번까지 통과했다면 input에서 bomb위치를 찾고, bomb를 지운 adjinput을 재귀로 보내준다.
      4. result값을 출력한다

   2. Stack (Stringbuilder 필수 == 메모리 절약)

      1. character를 담는 stack을 생성한다.
      2. input을 for문으로 탐색하면서 charAt값을 stack에 저장한다.
      3. stack의 size가 bomb의 길이보다 높거나 같다면 stack의 맨 윗 부분만 bomb와 비교하여, stack의 맨 윗 부분에 bomb와 같은 내용이 들어가 있으면 제거한다.
      4. 반복문이 끝나고 stack이 비어있으면 FRULA를, else라면 stack의 0번째 인덱스 값 부터 Stringbuilder에 담아 출력한다.

4. 재귀 방식은 메모리초과를 받았지만, stack 방식으로는 Stringbuilder를 사용해야 메모리초과를 면할 수 있었다.

소스코드

import java.io.*;
import java.util.*;
public class boj9935 {
    public static String result ="";
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        String bomb = br.readLine();
        solutionRecursion(input, bomb);
        System.out.println(result);
    }
    public static void solutionStack(String input, String bomb){
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < input.length(); i++) {
            stack.push(input.charAt(i));
            if(stack.size() >= bomb.length()){
                boolean isTrue = true;
                for (int j = 0; j < bomb.length(); j++) {
                    if(stack.get(stack.size()- bomb.length() + j) != bomb.charAt(j)){
                        isTrue = false;
                        break;
                    }
                }
                if(isTrue){
                    for (int j = 0; j < bomb.length(); j++) {
                        stack.pop();
                    }
                }
            }
        }
        if(stack.isEmpty()){
            result = "FRULA";
        }else {
            StringBuilder sb = new StringBuilder();
            for (Character c: stack){
                sb.append(c);
            }
            result = sb.toString();
        }
    }
    public static void solutionRecursion(String input, String bomb){
        if(!input.contains(bomb)){
            result = input;
  			return;
        }
        if(input.equals(bomb)){
            result = "FRULA";
            return;
        }
        for (int i = 0; i < input.length(); i++) {
            boolean istrue = false;
            if (input.charAt(i) == bomb.charAt(0)) {
                for (int j = 0; j < bomb.length(); j++) {
                    if (input.charAt(i+j) != bomb.charAt(j)) {
                        istrue = false;
                        break;
                    }
                    istrue = true;
                }
            }
            if (istrue) {
                String adjinput = input.substring(0, i) + input.substring(i + bomb.length(), input.length());
                solutionRecursion(adjinput, bomb);
            }
        }
    }
}

문제 핵심

• 문자열
• 스택