[JAVA] 백준 9935 - 문자열폭발

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

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        String t = br.readLine();
        char[] cArr = s.toCharArray();
        char std = t.charAt(t.length()-1);
        StringBuilder sb = new StringBuilder();
        int len = s.length();
        for (int i = 0; i < len; i++) {
            char c = cArr[i];
            sb.append(c);
            if(std==c) {
                if(checkC(sb, t)){
                    for (int j = 0; j < t.length(); j++) {
                       sb.deleteCharAt(sb.length()-1);
                    }
                }
            }
        }
        System.out.println(sb.length()==0?"FRULA":sb);
    }
    static boolean checkC(StringBuilder sb, String t) {
        int tlen = t.length();
        if(sb.length()<tlen) return false;
        int idx = sb.length()-1;
        for (int i = tlen-1; i >=0 ; i--) {
            if(sb.charAt(idx)!=t.charAt(i)){
                return false;
            }
            idx--;
        }
        return true;
    }
}

처음에 이 문제를 봤을 때 입력으로 주어지는 문자열의 길이가 최대 100만 자리인것을 보고, ReplaceAll을 n번 써서 답을 출력하면 시간초과를 내겠구나! 하고 Stack<Character>을  이용해 매 입력마다 타겟문자열과 일치하는지 체크하는 로직으로 해결하려고 했다.

근데 해당 방법이 메모리 초과가 나서 타겟 문자열 체크 로직 호출 횟수를 줄여보고 했는데 계속 메모리 초과가 났다. 

실제로 String객체를 만들지도 않고, StringBuilder를 이용해서 체크로직당 1회만 만들었는데 메모리 초과가 계속 나니까 boxing된 char를 가지는 스택이 문제겠거니 하고 char 배열을 이용해서 비슷한 로직을 만들어봤는데 이번엔 시간초과가 났다.

 

마지막으로 StringBuilder의 delete함수를 스택처럼 마지막자리만 삭제하도록 O(1) 시간복잡도로 사용했더니 겨우 통과했다.

만만하게 보다가 스트레스를 많이 받은 문제였다.

 

Boxing된 객체를 담는 컬렉션의 메모리 관련 정보를 좀 더 봐야할 것 같다.