boj9935

문제 풀이

문자열이 폭발 문자열을 포함 하고 있는 겨웅 모든 폭발 문자열이 폭발
넘은 문자열을 순서대로 이어 붙여 새로운 문재열을 만든다
새로 생긴 문자열에 폭발 문자열이 포함되어 있을수 있다.
폭발은 폭발 문자열이 문자열이 없을때 까지 계속된다.

1. 문자열 및 폭발 문자열을 받는다.
2. 문자열에 해당 문자열이 있는지 파악한다.
3. 문자열에 해당 index 가 몇번째로 오는지 파악한다.
4. 해당 문자열을 제거하고 문자열을 재구성한다.
5. 폭발 문자열이 없을때 까지 2~4 번을 반복한다.

1. queue 2 개를 만들고 각 큐를 돌며 해당 문자열을 찾고 있으며 다음 큐에 담고 true
   없으면 false

2. false 이면 반복문 종료

다음같이 문자열에 해당 폭발 문자열 존재 여부 확인후
처음 오는 인덱스를 파악후 지우고 문자열을 다시 생성해 위를 반복하는 식으로 문제를 파악하고 접근하였다.

코드

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

        // 1. 문자열 입력
        String input = br.readLine();
        // 폭발 문자열 입력
        String bum = br.readLine();



        while(input.contains(bum)){ // 2. 문자열에 폭발 문자열이 있는지 확인
            int startIndex = input.indexOf(bum); // 3. 문자열에서 폭발 문자열 가장 먼저 오는 것을 ㅊㅈ음
            char[] arr = new char[input.length()];

            for(int i =0; i<arr.length; i++){
                arr[i] = input.charAt(i);
            } // 배열 arr 에 저장

            for(int i=startIndex; i<startIndex+bum.length(); i++){
                arr[i] = ' ';
            }
            StringBuilder sb = new StringBuilder();
            for(int i=0; i<arr.length; i++){
                if(arr[i] != ' '){
                    sb.append(arr[i]);
                }
            } // 해당 문자열 제거
            input = sb.toString(); // 다시 돌리기 위해 input 문자열 제거 값으로 두기
        }
        if(input.equals("")){
            System.out.println("FRULA");
        }else{
            System.out.println(input);
        }
    }
}

---

허나 다음과 같이 풀면 메모리 초과로 실패를 한다
역시 불변객체란

그래서 다른사람의 코드를 참고하였다.

Stack을 쓰는 방식

문제 풀이 2

stack을 쓰는 방식은
1. 문자열을 차례로 스택에 넣는다
2. 문자열이 폭발 문자열 보다 같거나 길어지면
stack에 담긴 문자열과 폭발 문자열과 비교해서 같은 문자열이면
stack.pop을 해준다.

즉 문자열을 계속 저장해주면서 폭발 문자열 보다 길때만 pop 해주며 되는 방식이다.

코드 2

package 알고리즘5주차;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.sql.Statement;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class boj9935 {
    private static String input;
    private static String bum;

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

        // 1. 문자열 입력
         input = br.readLine();
        // 폭발 문자열 입력
         bum = br.readLine();

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

             boolean check  = false;
             if(stack.size() >= bum.length()){
                 // 스택에서 제거
                 for(int j=0; j<bum.length(); j++){
                     if(bum.charAt(j) != stack.get(stack.size()-bum.length()+j)){
                         check = true; // 같지 않은게 있다면 true
                         break;
                     }
                 }
                 if(!check){ // true 있다면 스텍에서 지우기
                     for(int j=0; j<bum.length(); j++ ){
                         char c  = stack.pop();
                     }
                 }
             }

         }
         if(stack.isEmpty()){
             System.out.println("FRULA");
         }else{
             StringBuilder sb = new StringBuilder();
             for(Character c : stack){
                 sb.append(c);
             }
             System.out.println(sb);
         }
    }


}