Stack - 9935 문자열 폭발

GoRuth·2025년 6월 1일

문제 설명

이번 문제는

폭발 문자열을 포함하는 경우 폭발

남은 문자열은 이어붙여 새로운 문자열을 만듬

폭발 문자열이 없을 때까지, 1ㆍ2 반복

폭발 문자열이 없는 문자열 print / 문자열이 없다면 "FAULA" print

을 해야하는 문제입니다.

replaceAll() -> 실패

코드

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        String s = br.readLine();

        while (!str.equals(str.replaceAll(s, ""))) {
            str = str.replaceAll(s, "");
        }

        System.out.println(str.isEmpty() ? "FRULA" : str);
    }
}

결과

이유

1. replaceAll 로직
-> Pattern.compile(regex) -> Matcher.find() -> 문자열 새로 생성
2. 반복적으로 새 문자열을 만듬
-> 매번 문자열 전체 복사 + 패턴 매칭 진행
3. Java의 String은 불변 객체
-> 매 replaceAll마다 새 문자열을 생성해야 합니다.

즉, replaceAll()을 사용하면 반복적으로 새 문자열을 만들면서 메모리가 초과되는 상황이 발생하게 됩니다.

StringBuilder() - 성공

import java.io.*;
import java.util.*;

public class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br =
        new BufferedReader(new InputStreamReader(System.in));
    String str = br.readLine();
    String target = br.readLine();
    int tLen = target.length();

    StringBuilder result = new StringBuilder();

    for (int i = 0; i < str.length(); i++) {
      result.append(str.charAt(i));

      // 마지막 부분이 폭탄 문자열과 같다면 삭제
      if (result.length() >= tLen) {
        boolean isMatch = true;

        for (int j = 0; j < tLen; j++) {
          if (result.charAt(result.length() - tLen + j) != target.charAt(j)) {
            isMatch = false;
            break;
          }
        }

        if (isMatch) {
          result.delete(result.length() - tLen, result.length());
        }
      }
    }

    System.out.println(result.length() == 0 ? "FRULA" : result);
  }
}

결과

이유

1. 코드 로직 (append -> 폭탄 유무 판단 -> delete)
-> 새로운 문자열을 만드는 작업 ❌
2. append(), delete(), insert() 등의 동작의 System.arraycopy()
-> 배열을 메모리 단위로 복사, 덮어쓰기를 진행 (불필요한 객체 생성은 피하려고 설계)

즉, StringBuilder()을 사용하면 주기적으로 문자열을 수정해도 새로운 객체를 생성하지 않아서 메모리 초과가 발생하지 않습니다.

StringBuilder()

내부구조

char[] value;
int count; // 현재 길이

메소드

append(value) -> 맨 뒤에 value 저장
insert(idx, value) -> idx위치에 value 저장

charAt(index) -> 해당 index의 데이터 return
indexOf(str) -> str이 처음으로 나오는 index return
indexOf(str, index) -> index부터 시작해서 str이 처음으로 나오는 index return

delete(startIdx, endIdx) -> startIdx부터 endIdx - 1까지 삭제
deleteCharAt(index) -> 해당 index의 데이터 삭제

length() -> 현재 길이