[백준] 9935번 문자열 폭발

9953번 문자열 폭발

1. 이해하기

• 폭발 문자열이 발견되면 그 문자열을 없애버려야 한다.
• 스택의 개념을 쓰는 문제이다.
• 가장 중요한 String +연산은 시간과 메모리가 많이 쓰인다는 것을 알아야 한다.

---

2. 전체 코드

• 주석의 코드를 실행하면 시간이 오래 걸린다. 그 이유가 모든 문자에 대해서 print를 하는데 시간이 걸리기 때문이다.(추측)

• 이를 줄이기 위해서는 StringBuilder를 사용하면 된다.

  package algo;
  //
  //import java.io.BufferedReader;
  //import java.io.IOException;
  //import java.io.InputStreamReader;
  //
  //public class Acm9935 {
  //    static char[] cStk = new char[1000000];
  //    static int cStkIdx = -1;
  //    static char[] str;
  //    public static void main(String[] args) throws IOException {
  //        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  //        str = br.readLine().toCharArray();
  //        char[] bomb = br.readLine().toCharArray();
  //        int now = 0;
  //        for(int i = 0; i < str.length; i++) {
  //            if(bomb[now] == str[i]) {
  //                now++;
  //                cStk[++cStkIdx] = str[i];
  //                if(now == bomb.length) {
  //                    for(int j = 0; j < now; j++) {
  //                        cStkIdx--;
  //                    }
  //                    now = 0;
  //                    for(int j = cStkIdx-bomb.length; j <= cStkIdx; j++) {
  //                        if(j < 0) continue;
  //                        if(cStk[j] == bomb[now]) {
  //                            now++;
  //                        } else {
  //                            now = 0;
  //                            if(bomb[now] == cStk[j])
  //                                now++;
  //                        }
  //                    }
  //                }
  //                
  //            } else {
  //                now = 0;
  //                if(bomb[now] == str[i])
  //                    now++;
  //                cStk[++cStkIdx] = str[i];
  //            }
  //        }
  //        if(cStkIdx == -1)
  //            System.out.println("FRULA");
  //        else {
  //            for(int i = 0; i <= cStkIdx; i++)
  //                System.out.print(cStk[i]);
  //        }
  //    }
  //}
  

package algo;

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

public class Acm9935_문자열폭발 {
    static int[] stk = new int[1000000];
    static char[] cStk = new char[1000000];
    static int stkIdx = -1;
    static int cStkIdx = -1;
    static char[] str;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        str = br.readLine().toCharArray();
        String bomb = br.readLine();
        int now = 0;
        for (int i = 0; i < str.length; i++) {
            if (bomb.charAt(now) == str[i]) {
                now++;
                stk[++stkIdx] = now;
                cStk[++cStkIdx] = str[i];
                if (now == bomb.length()) {
                    for (int j = 0; j < now; j++) {
                        stkIdx--;
                        cStkIdx--;
                    }
                    if (stkIdx != -1)
                        now = stk[stkIdx];
                    else
                        now = 0;
                }
            } else {
                now = 0;
                if (bomb.charAt(now) == str[i])
                    now++;
                stk[++stkIdx] = now;
                cStk[++cStkIdx] = str[i];
            }
        }
        if (cStkIdx == -1)
            System.out.println("FRULA");
        else {
            for (int i = 0; i <= cStkIdx; i++)
                System.out.print(cStk[i]);
        }

    }
}

---

4. 배운점

• 자바에서 String에 +연산을 계속하면 메모리 초과가 날 수 있으니 StringBuilder를 사용하던 다른 방법으로 String을 덧붙여야 한다.
• 이번에는 스택을 직접 구현함으로써 이 문제를 해결했다.
• 문자를 여러개 출력하는 일이 있으면 java에서는 무조건 StringBuilder를 써서 출력하자!