[JAVA] 백준 9935 문자열 폭발

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

문제분석

문자열 폭발 문제를 스택 방식으로 해결한 구현이다. 대상 문자열을 한 글자씩 읽어 stack 배열에 쌓고(top으로 스택 상단 관리), 새로 들어온 문자가 폭발 문자열의 마지막 문자와 같고 현재 길이가 폭발 문자열 길이 이상일 때만 스택의 뒤쪽 M개를 직접 비교한다. 실제로 폭발 문자열과 일치하면 top -= M으로 해당 부분을 즉시 제거하여 문자열을 잘라내는 효과를 낸다. 이 과정을 끝까지 반복한 뒤 스택이 비어 있으면 "FRULA", 아니면 남은 부분만 출력한다. ArrayDeque나, String을 활용하면 메모리 초과가 발생하는 문제이다. 따라서 char[] 배열만으로 구현해야 풀 수 있다.

 

코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] tArr = br.readLine().toCharArray(); // 대상 문자열
        char[] bArr = br.readLine().toCharArray(); // 폭발 문자열
        int N = tArr.length;
        int M = bArr.length;

        char[] stack = new char[N];
        int top = 0; // stack 상단 가리킴
        for (int i = 0; i < N; i++) {
            stack[top++] = tArr[i];
            if (top >= M && tArr[i] == bArr[M - 1]) {// 폭발 문자열 마지막 글자가 나오면, stack에서 peek해서 후보가 맞나 확인
                boolean flag = true;
                for (int j = 0; j < M - 1; j++) {// j로 stack 순회하면서 폭발문자열 가능한지 확인, 불가능하면 flag =false
                    if(stack[top - M + j] != bArr[j]){
                        flag = false;
                        break;
                    }
                }
                if(flag){
                    top -= M;
                }
            }
        }

        if (top == 0) System.out.println("FRULA");
        else System.out.println(new String(stack, 0, top));
    }
}