[백준] 문자열 폭발

시간복잡도 생각해보기

• 문자열의 총 길이가 10^6 이고 제한시간 2초이므로 2 X 10^8 개의 연산이 가능하다.
• 따라서 O(N^2)에서는 10^12 개의 연산이 필요하므로 제한시간 초과가 되므로 O(NlogN)에 해결해야 한다.

풀이 아이디어

• replace.All() 을 처음에 사용했으나, String은 불변 객체이므로 replaceAll은 내부적으로 새로운 문자열을 생성해 원본 문자열을 대체한다. 따라서 문자열의 크기가 10^6처럼 매우 크거나 대체 작업이 여러번 수행 될 경우에는 새로운 문자열 객체가 과도하게 사용 돼 메모리를 초과한다.
• 메모리를 효율적으로 사용하기 위해서는 Stack의 push, pop을 사용한다.
• 문자열을 charAt으로 나눠서 계속 stack에 푸쉬하다가, bomb의 문자길이와 비슷해지면 그때부터 비교작업을 수행한다.
• 비교작업: (Stack의 현재 사이즈 - bomb의 사이즈) + j (j는 0부터 bomb의 길이까지) char이 같은지 확인한다.
• 하나라도 다르다면 flag를 false로 둔다.

의사코드 / 풀이 과정

stack.push(carr[i]);
if(stack의 사이즈가 bomb의 사이즈보다 크거나 같다면):
    for(j=0부터 bomb의 사이즈까지):
          if(stack.get(스택 사이즈 - bomb사이즈 +j) != bomb.charAt(j)) -> 하나라도 다르면 false;
        만약 모두 같다면: 
           for(j=0부터 bomb의 사이즈까지):
                  stack.pop(); //스택에서 제거 

실제 코드

package BJ;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
public class 문자열_폭발 { 
    static Stack<Character> stack = new Stack<>();
    public static void main(String [] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char [] arr = br.readLine().toCharArray();
        String bomb = br.readLine();
        for(int i=0; i<arr.length;i++) {
            stack.push(arr[i]); //스택에 집어넣는다.
            if(stack.size() >= bomb.length()) { //제거해야하는 길이와 동일해지면 
                boolean flag = true;
                for(int j=0;j<bomb.length();j++) {
                    if(stack.get((stack.size()-bomb.length())+j) != bomb.charAt(j)) {
                        flag = false;
                    }
                }
                if(flag) { 
                    for(int j=0; j<bomb.length(); j++) {
                        stack.pop();
                    }
                }
            }    
        }
        StringBuilder sb = new StringBuilder();
        for(char c: stack) {
            sb.append(c);
        }
        String str = sb.toString() == "" ? "FRULA" : sb.toString();
        System.out.println(str);
    }
}

틀린 아이디어

String 문자열 = “”;
String 폭발문자열 = “”;

while(폭발문자열이 더이상 없을때까지): -> 시간초과 가능성있음 
       if(문자열.contain(폭발문자열)): 
        문자열 = 문자열 - 폭발문자열 

오류난 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class 문자열_폭발 { 
    public static void main(String [] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        String bomb = br.readLine();
        while(true) {
            if(!str.contains(bomb)) {
                break;
            }
            str = str.replaceAll(bomb, "");
        }
        if(str.isBlank() || str.isEmpty()) {
            System.out.println("FRULA");
            return;
        }
        System.out.println(str);
    }
}

추가시간이 2초인데 시간문제는 아닌것같고 replace.All() 때문에 메모리초과