[백준] 9935 문자열 폭발 - StringBuilder + 아이디어 JAVA

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

9935번: 문자열 폭발

코드설명

StringBuilder를 활용하고, 시간초과가 나지 않기 위해 코드를 짜야합니다.

 

문제를 보면, replaceAll을 활용하여 쉽게 해결할 수 있지만 replaceAll을 활용할경우 새로운 String 메모리 배열이 계속해서 선언되면서 메모리초과가 납니다. 그러므로 아래처럼 StringBuilder를 활용하여 문자를 하나하나씩 앞에서 넣어가며 진행합니다.

 

이 문제에서 처음 접해본 방식의 로직입니다.

1. arr을 하나하나씩 sb에 넣습니다.

2. sb의 길이가 bombstr보다 길어진다면, bombstr과 sb를 비교합니다. 

    2.1 만약에 일치하지 않는다면, 넘어갑니다.

    2.2 일치한다면 해당 bombstr을 delete 합니다.

 

위의 로직을 반복하면 되는데, arr을 하나하나씩 넣으면서 비교하며 sb가 bombstr보다 길어질때만 비교를 하는것을 유의합니다. 

또한, 로직을 반복하며, 아래의 코드처럼 sb의 char을 sb.length() - bombstr.length() 로 처리하는것을 볼 수 있습니다. 아래의 범위를 통하여 이전에 검사했던 부분들은 해당 되지 않으니 필요한 부분들만 검사하며 시간을 줄입니다.

for(int j=0;j<bombstr.length(); j++) {
    char sbChar = sb.charAt(sb.length() - bombstr.length() + j);
    char bombChar = bombstr.charAt(j);
    if(sbChar != bombChar) {
        notSameFlag = true;
        break;
    }
}

 

코드

StringBuilder를 활용하여 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	public static int R, C;
	public static String arr, bombstr;
	public static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine()); 	
    	
    	arr = st.nextToken();
    	st = new StringTokenizer(br.readLine());
    	bombstr = st.nextToken();
    	
    	boolean notSameFlag = false;
        
        for(int i=0;i<arr.length();i++) {
            sb.append(arr.charAt(i));

            if(sb.length() >= bombstr.length()) {
                notSameFlag = false;
                for(int j=0;j<bombstr.length(); j++) {
                    char sbChar = sb.charAt(sb.length() - bombstr.length() + j);
                    char bombChar = bombstr.charAt(j);
                    if(sbChar != bombChar) {
                        notSameFlag = true;
                        break;
                    }
                }

                if(notSameFlag == false) { //포함된경우
                    sb.delete(sb.length() - bombstr.length(), sb.length());
                }
            }

        }
    
    	
    	if(sb.length() == 0)
    		System.out.println("FRULA");
    	else
    		System.out.println(sb);
    }
}

 

 

replaceAll을 활용하여 짠 코드 ( 메모리 초과 ) 

메모리초과가 나는 이유는 replaceAll 이 계속해서 새로운 String을 Return 해주면서 메모리에 할당시켜 그렇습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	public static int R, C;
	public static String arr, bombstr;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine()); 	
    	
    	arr = st.nextToken();
    	
    	st = new StringTokenizer(br.readLine());
    	bombstr = st.nextToken();
    	
    	while(arr.contains(bombstr)) {
    		arr = arr.replaceAll(bombstr, "");

    	}
    	if(arr.length() == 0)
    		System.out.println("FRULA");
    	else
    		System.out.println(arr);
    }
}