[백준] 9935번 - 문자열 폭발 (Java)

 

<문제 분석>

1. 문자열을 폭발문자열로 split 한 다음 머지하자.

2. 머지한 문자열을 다시 재귀호출하자.

  2-1. 문자열에서 폭발문자열이 없으면 문자열 리턴

  2-1. 문자열의 사이즈가 0이면 "FRULA"리턴

 

<코드 구현>

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

/*
[백준] 9935번 - 문자열 폭발 (Java)
*/

public class Main {
    static String str, bom;
    
    void InputData() {
        Scanner in = new Scanner(System.in);
        str = in.next();
        bom = in.next();
     }

    String DFS(String s) {
        if (!s.contains(bom)) {
            if (s.length() == 0) return "FRULA";
            return s;
        }
        String[] string = s.split(bom);
        String merge = "";
        for (String x : string) {
            merge += x;
        }
        return DFS(merge);
    }

    void Solve() {
        System.out.println(DFS(str));
    }

	public static void main(String[] args) {
        Main m = new Main();
        m.InputData();
        m.Solve();
	}
}

 

<제출 결과>

 

<결과 분석>

메모리 초과가 발생했다. 문자열의 길이가 < 1,000,000이니까 string끼리 머지하는 것은 비효율적임.

StringBuilder를 사용해 봤으나 여전히 메모리 초과가 발생한다.

문자열을 스택에서 저장해서 폭발문자열 길이만큼 쌓이면 비교하는 방식으로 구현해서 통과했다.

 

<코드 구현 - 스택>

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

/*
[백준] 9935번 - 문자열 폭발 (Java)
*/

public class Main {
    static String org, bomb;
    
    void InputData() {
        Scanner in = new Scanner(System.in);
        org = in.next();
        bomb = in.next();
     }

    // 1. contains()를 재귀호출로 사용하는 방법
    String DFS(String s) {
        if (!s.contains(bomb)) {
            if (s.length() == 0) return "FRULA";
            return s;
        }
        String[] string = s.split(bomb);
        StringBuilder sb = new StringBuilder();
        // String merge = "";
        for (String x : string) {
            sb.append(x);
        }
        String merge = sb.toString();
        
        return DFS(merge);
    }

    void Solve() {
        //System.out.println(DFS(str));
        // 2. 스택으로 구현
        Stack<Character> stack = new Stack<>();
        for (int i=0; i<org.length(); i++) {
            stack.push(org.charAt(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;
                        break;
                    }
                }
                if (flag) { // 일치하면 폭발문자열 길이만큼 스택에서 제거
                    for (int k=0; k<bomb.length(); k++) {
                        stack.pop();
                    }
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for (char ch : stack) {
            sb.append(ch);
        }

        System.out.println(sb.length()>0?sb.toString():"FRULA");
    }

	public static void main(String[] args) {
        Main m = new Main();
        m.InputData();
        m.Solve();
	}
}

 

<제출 결과>