Baekjoon 9935 문자열 폭발 - 메모리 초과

더 깔끔한 노션을 원한다면

Baekjoon 9935 문자열 폭발 - 메모리 초과

9935번: 문자열 폭발

String 메모리 초과 때문에 마음 고생을 하게 했던 문제.

처음 생각 - contains, replace

문제 보고 바로 떠오른건 contains, replace였다.

private static void P9935() throws Exception {
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  String answer = "";
  String string = br.readLine();
  String boomString = br.readLine();
  while(string.contains(boomString)) {
    string = string.replaceAll(boomString, "");
  }
  if(string.length() == 0){
    System.out.println("FRULA");
  } else {
    System.out.println(string);
  }
}

하지만 바로 메모리 초과!😂

힌트를 보니 스택으로 분류되어 있었다.

역시 스택❗

1. stack에 문자열(string)을 차례로 넣어준다.

for (int index = 0; index < length; index++) {
  stack.push(string[index]);
  if (stack.size() >= bombLength) {
    if (isBomb(stack, bomb)) {
      for (int b = 0; b < bombLength; b++) {
        stack.pop();
      }
    }
  }
}

2. stack의 크기가 bomb 크기와 같아지면 터질 수 있는지 검사해준다.(isBomb)

private static boolean isBomb(Stack<Character> stack, String bomb) {
  for (int index = 0; index < bomb.length(); index++) {
    if (stack.get(stack.size() - bomb.length() + index) != bomb.charAt(index)) {
      return false;
    }
  }
  return true;
}

메모리 초과 이유❗

String.replaceAll (regex, replacement) 접근 방식을 사용하면 한 번의 호출로 겉보기에는 교체를 수행 할 수 있지만 내부적으로 많은 추가 GC(Garbage Collection) 적격 객체가 생성된다.

따라서 문자열 교체 문제는 replace가 아닌 다른 방법을 생각하는 것이 좋다!

전체 코드

/**
 * @처음생각 contains, replaceAll을 사용 => 메모리 초과(string GC)
 * @포인트 스택으로 해결
 */
import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Main {
  public static void main(String[] args) throws java.lang.Exception {
    System.out.println(P9935());
  }

  private static String P9935() throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    Stack<Character> stack = new Stack<>();
    char[] string = br.readLine().toCharArray();
    String bomb = br.readLine();

    int length = string.length;
    int bombLength = bomb.length();
    for (int index = 0; index < length; index++) {
      stack.push(string[index]);
      if (stack.size() >= bombLength) {
        if (isBomb(stack, bomb)) {
          for (int b = 0; b < bombLength; b++) {
            stack.pop();
          }
        }
      }
    }
    StringBuilder sb = new StringBuilder();
    for (Character ch : stack) {
      sb.append(ch);
    }
    if (sb.length() == 0) {
      return "FRULA";
    } else {
      return sb.toString();
    }
  }

  private static boolean isBomb(Stack<Character> stack, String bomb) {
    for (int index = 0; index < bomb.length(); index++) {
      if (stack.get(stack.size() - bomb.length() + index) != bomb.charAt(index)) {
        return false;
      }
    }
    return true;
  }
}