백준 9935번 문자열 폭발

메모리 초과 발생 코드

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 boom = br.readLine();
        int boomlen = boom.length();
        StringBuilder sb = new StringBuilder();
        Stack<Integer> stack = new Stack<>();
        sb.append(str);
        boolean flag;
        while (true){
            flag = false;
            int len = sb.length()-boomlen;
            for (int i = 0; i <= len; i++) {
                String temp = sb.substring(i,i+boomlen);
                if(temp.equals(boom)){
                    stack.add(i);
                    flag = true;
                    i += boomlen;
                }
            }
            while (!stack.isEmpty()){
                int index = stack.pop();
                sb.delete(index,index+boomlen);
            }
            if(!flag){
                if(sb.length()==0){
                    System.out.println("FRULA");
                }
                else {
                    System.out.println(sb);
                }
                return;
            }
        }
    }
}

정답 코드

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


public class StringExplosion {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        String boom = br.readLine();
        StringBuilder sb = new StringBuilder();

        for(int i=0; i<str.length(); i++) {
            char ch = str.charAt(i);
            sb.append(ch);
            if(sb.length() >= boom.length()) { 
                boolean sameFlag=true;
                for(int j=0; j<boom.length(); j++) {
                    char ch1 = sb.charAt(sb.length() - boom.length() + j);
                    char ch2 = boom.charAt(j);
                    if(ch1 != ch2) {
                        sameFlag = false;
                        break;
                    }
                }
                if(sameFlag) {
                    sb.delete(sb.length()-boom.length(), sb.length());
                }
            }
        }

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

풀이방법

이 문제는 문자열을 폭탄 문자열과 비교해가며, 같다면 지우는것을 반복하는 어렵지 않은 문제이다.
하지만, substring, replace, split의 메서드 사용시 오류가 난다.
이유는 String temp = sb.substring(i,i+boomlen);에 있다.
📢 자바의 String은 불변(immutable)이라서 값을 바꿀때마다 매번 새로운 String을 할당한다.
따라서 메모리를 계속 추가로 사용하게 되는 것이다.

그래서 string대신 char로 변환해서 문제를 푸는 방식을 선택하였다.

1. 입력문자열을 하나씩 char로 변환해서 stringBuilder에 넣어준다.
2. sb의 길이가 폭탄 문자열의 길이 이상이 되면, 비교를 시작한다.
3. 비교했을때, sb와 폭탄 문자열이 같다면, sb에서 그 값만큼 삭제해준다.
4. 1번으로 돌아가 문자열의 마지막까지 반복한다.

후기

구현 자체가 어려운 문제는 아니다.
StringBuilder의 자주 사용하지 않는 여러 메서드를 활용할 수 있었다.
📢 자바의 String은 불변(immutable)이라서 값을 바꿀때마다 매번 새로운 String을 할당한다.
이부분을 이 문제를 통해 얻을 수 있는것이 핵심인것 같다.