Baekjoon 9935 문자열 폭발

문제 이해

주어진 문자열에서 특정 문자열이 있으면 없애고 없앤 것으로 인해 앞 뒤 문자열이 붙어서 또 특정 문자열이 만들어질 수 있으므로 반복해서 확인해야 한다.

입출력 조건 확인

문자열 한바퀴 돌면 되니까 별 상관 없지 않을까..? 했는데…

했는데…

문제 풀이 내용 정리

tmp를 하나 만들고 거기에 주어진 문자열을 넣으면서 폭탄이 있는지 확인하면 될 것 같았다.

결과적으로 정상적인 결과는 나오지만 백준에서 1%도 못 넘기고 메모리 초과로 튕겨냈다.

Java

import java.util.Scanner;

public class Main {
    public static String string_cut(String string, int start, int end) {
        String tmp = new String();

        for (int i = start; i < end; i++) {
            tmp += string.charAt(i);
        }
        return tmp;
    }

    public static void main(String[] args) throws Exception {
        String line = new String();
        String bomb = new String();
        Scanner sc = new Scanner(System.in);

        line = sc.nextLine();
        int lineSize = line.length();
        bomb = sc.nextLine();
        int bombSize = bomb.length();

        int tmpPoint = 0;
        int linePoint = 0;
        String tmp = new String();
        
        while (true) {
            if (tmp.length() < bombSize) {
                if (linePoint < lineSize) tmp += line.charAt(linePoint);
            } else {
                if (tmp.charAt(tmpPoint - bombSize) == bomb.charAt(0)) {
                    if (bomb.equals(string_cut(tmp, tmpPoint - bombSize, tmpPoint))) {
                        tmp = tmp.substring(0, tmpPoint - bombSize);
                        tmpPoint -= bombSize;
                    }
                }
                if (linePoint < lineSize) tmp += line.charAt(linePoint);
            }
            tmpPoint++;
            linePoint++;

            if (linePoint > line.length()) {
                break;
            }
        }
        if (tmp.length() == 0) {
            System.out.println("FRULA");
        } else {
            System.out.println(tmp);
        }
    }
}

코드 문제점 및 해결 방법

찾아보니 String이 메모리 상에서 불변하는 자료형이라고 한다.

수정을 하면 수정이 되는 게 아니라 새로 만들고 거기로 주소를 이어주는 방식으로…

그래서 StringBuilder를 쓰면 된다고 하는데…

알고리즘 개발에서 이런걸 하는 게 맞나..?