아이디어

• 문자열을 한 글자씩 넣는다. 넣을 때마다 stack 맨 윗부분의 l 글자가 폭발 문자열인지 본다. (l은 폭발 문자열의 길이)
  • 시간복잡도: $O(nl)$ (n은 문자열의 길이)
  • 36×100만 정도이므로 가능
• 주의: StringBuffer에 출력 결과를 저장할 때 sb.insert(0, c)(시간복잡도 $O(n)$) 대신 sb.append()를 사용하고, 역방향 iterator를 sb.reverse()로 가져오는 방법을 사용해야 한다.

코드

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

public class Main {
    static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();

    static char[] s, x;
    static int l;
    static MyStack stack = new MyStack();

    public static void main(String[] args) throws Exception {
        s = rd.readLine().toCharArray();
        x = rd.readLine().toCharArray();
        l = x.length;

        for (char c : s) {
            stack.push(c);
            if (stack.check(x))
                stack.erase(l);
        }
        while (stack.size > 0) {
            sb.append(stack.pop());     // 역방향으로 append
        }

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

    static class MyStack {
        char[] data = new char[1000000];
        int size = 0;

        void push(char c) {
            data[size++] = c;
        }

        void erase(int cnt) {
            size -= cnt;
        }

        char pop() {
            if (size == 0) return 0xFF;
            return data[--size];
        }

        boolean check(char[] x) {
            if (size < l) return false;
            for (int i=1; i<=l; i++) {
                if (data[size-i] != x[l-i])
                    return false;
            }
            return true;
        }
    }
}

메모리 및 시간

• 메모리: 27288 KB
• 시간: 408 ms

리뷰

• 아이디어 자체는 실버 급인데, 잔실수가 많아서 많이 틀렸다.
• 처음 실수: stack size를 int가 아닌 char로 저장함
• 두 번째 실수: sb.insert(0, c)를 사용함