코테-boj 9935

boj 9935

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

try1

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));
        String str=br.readLine();
        String bomb=br.readLine();

        boolean bombFlag=true;
        
        
        while(bombFlag){
            int idx=str.indexOf(bomb);
            if(idx>-1){
                str=str.substring(0,idx)+
                        str.substring(idx+bomb.length(),str.length());
            }
            else{
                bombFlag=false;
            }
        }

        if(str.isBlank()){
            System.out.println("FRULA");
        }
        else {
            System.out.println(str);
        }
    }
}

-가장 먼저 떠오른 건 위처럼 substring으로 추출하거나
replace()로 해당되는 문자열을 삭제하는 것이었는데 메모리 초과가 나버렸다.

try2

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));
        String line=br.readLine();
        String bomb=br.readLine();

        Stack<Character> stk=new Stack<>();
        char[] str=line.toCharArray();
        char[] bombStr=bomb.toCharArray();

        for(int i=str.length-1;i>=0;i--){
            stk.push(str[i]);
            //bomb의 앞글자와 같음
            if(stk.get(stk.size()-1)==bombStr[0] && stk.size()>=bomb.length()){
                //bomb와 같은지 검사
                Boolean isbomb=true;

                for(int j=0;j<bombStr.length;j++){
                    if(stk.get(stk.size()-1-j)!=bombStr[j]){
                        isbomb=false;
                    }
                }
                //폭탄포함으로 삭제하기
                if(isbomb){
                    //bomb pop
                    for(int k=0;k<bomb.length();k++){
                        stk.pop();
                    }
                }
            }
        }

        StringBuilder sb=new StringBuilder();

        int len=stk.size();
        for(int i=0;i<len;i++){
            sb.append(stk.pop());
        }

        String ans= sb.toString();
        if(ans.isBlank()){
            System.out.println("FRULA");
        } else{
            System.out.println(ans);
        }
    }
}

• substring을 사용할 떄 메모리가 많이 사용되는 건가 해서 replace로 바꿔도 메모리 초과가 났다. 그래서 찾아보니 stack을 이용하는게 메모리면에서 낫다고 한다.
  stack을 이용하면 문자열을 전부 다 넣은 다음 검사하는게 아니라 넣어가는 과정에서 검사해 폭발시키는 것이 가능하니 확실히 메모리 면에서 이 방법이 맞을 것 같았다.
• 나는 폭발문자열의 맨 앞부분과 같은 문자열이 push되면 폭발문자열인지 검사해 맞다면 pop하는 방식으로 구현했다.

피드백

• 생각해보니 try2의 방식대로 bomb의 맨앞 문자열과의 일치여부로 검사해서 하나씩 넣어가는 것을 처음부터 생각했다면 꼭 stack이 필요하지는 않았을 거 같다. (그냥 char[]의 index를 조정해서 폭발이후를 새로 저장해나갈 수도 있었다.)

• replace,substring등의 string함수들이 메모리를 꽤 잡아먹는다는 것을 인지했다. substring,replace 는 String이 불변객체이기에 참조하는 char[]을 바꾸는 방식이다. 내 생각으로는 128MB의 허용치면 1000000정도의 String은 2개가 되더라도 저장된후 바로 가비지컬렉트되면 메모리 초과할 정도의 양이 나오진 않을 것 같은데 GC가 매번 바로 동작하는 것은 아닌 듯하다.
  https://kimfk567.tistory.com/114

• String str=str1+str2와 같은 방법은 메모리 소모가 크다.
  String은 불변객체이기에 그 안의 참조되는 char[]이 바뀌고 기존의 char[]이 가비지 컬렉트되는 방식이다. 반면 StringBuilder는 참조하는 배열객체가 그대로이고 그 내용을 바꾸는 방식으로 메모리 소모가 적다.
  참고:https://okky.kr/article/344591?note=1105597
  https://go-coding.tistory.com/9
  http://sungjinlee.blogspot.com/2013/12/blog-post.html

• c++에서의 stack은 index로 접근하는 것이 없었던 걸로 기억하는데 java의 stack은 get()으로 검사가 가능했다. 하지만 시간복잡도가 상대적으로 높으니 남발하지 않아야한다.