[백준 9935] 문자열 폭발

 

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

---

• 문제설명
  문자를 한 줄 입력받고 다음줄에 또 문자를 입력받는다. 만약 첫번째 문자열에 두번째 문자열이 포함되어 있으면 해당 문자열을 삭제해주고 삭제 한 부분을 빼고 남은 문자들을 이어준다. 만약 이었을 때 또 다시 포함되어 있다면 위 과정을 계속 진행한다. 포함되어 있지 않을 때 까지 진행하고 만약 모두 지웠는데 문자열의 길이가 0이면 "FRULA"를 출력한다.

• 제출코드     

import java.util.*;

public class Main {
    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//
//        String str = sc.next();
//        String bomb = sc.next();
//
//        String answer = "";
//        int len = bomb.length();
//
//        while(str.contains(bomb)){
//            int idx = str.indexOf(bomb);
//            str = str.substring(0,idx)+ str.substring(idx+len);
//        }
//        if(str.length() != 0) System.out.println(str);
//        else System.out.println("FRULA");
        Scanner sc = new Scanner(System.in);

        String str = sc.next();
        String bomb = sc.next();

        StringBuilder sb = new StringBuilder();
        int len = bomb.length();

        for (int i = 0; i < str.length(); i++) {
            sb.append(str.charAt(i));  // 문자열을 한 글자씩 StringBuilder에 추가

            // 현재 StringBuilder의 마지막 부분이 bomb와 일치하는지 확인
            if (sb.length() >= len && sb.substring(sb.length() - len).equals(bomb)) {
                sb.delete(sb.length() - len, sb.length());  // 일치하는 부분 제거
            }
        }

        // 남은 문자열이 있으면 출력하고, 없으면 "FRULA" 출력
        if (sb.length() != 0) System.out.println(sb.toString());
        else System.out.println("FRULA");
    }

 

• 코드설명
  먼저 문자들을 입력받고 두번째 문자의 길이를 구한다. 이는 첫번째 문자열에서 두번째 문자열을 삭제할 때 사용하기 위해서다. for문을 통해 문자들을 StringBuilder에 넣어주고 넣으면서 마지막 문자가 bomb와 같은 지 확인한다.
  만약 같다면, 마지막 일치하는 부분을 delete를 사용해 삭제해준다.

---

• 마무리
  처음에는 위 주석처럼 문제를 풀었는데 메모리 초과가 났었다. 메모리 초과가 왜 나는지 궁금했는데 str문자열에서 bomb문자를 찾을 때마다 메모리에 새로운 문자열 객체가 계속 생성되기 때문이다. 객체가 계속 생성되어 메모리에 쌓이다 보니 메모리 사용량이 증가해서 답은 맞아도 통과를 받을 수 없었다.
  이를 해결하는 방법이 바로 StringBuilder이다. 
  StringBuilder는 String과는 달리 가변적이므로 문자열을 동적으로 수정하는 데 좋다.
  문자열 관련 문제들 좀 많이 풀어 보면서 StringBuilder에 익숙해져야겠다.