[백준] 9935번 문자열 폭발 (자바 풀이)

문제

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

9935번: 문자열 폭발

풀이

처음에는 자바 String의 split() 기능을 이용해서 쉽게 해결하려고 했다. 하지만 이 방법을 사용하면 메모리 초과가 발생해버린다. 그 이유는 자바의 String은 불변(immutable)이라서 값을 바꿀때마다 매번 새로운 String을 할당하기 때문이다. 

 

따라서 이 문제는 스택 혹은 StringBuilder를 이용해서 풀어야한다.

 

풀이는 간단하다. 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 boom = br.readLine();
        
        /* 메모리 초과 */
        while(true) {
            String[] arr = str.split(boom);
            if(arr.length == 0) {
                System.out.println("FRULA");
                return;
            }else if(arr.length ==1) {
                System.out.println(arr[0]);
                return;
            }else {
                StringBuilder sb = new StringBuilder();
                for(int i=0; i<arr.length; i++) {
                    sb.append(arr[i]);
                }
                str = sb.toString();
            }
        }
    }
}

아래 코드가 맞는 방법

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 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()) {    // sb의 길이가 boom 이상이 되면 확인
                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.toString());
        }
    }
}
 

결과