[BaekJoon] 9935번 문자열 폭발 (Java) 문제 풀이 [Gold 4]

문제

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

9935번: 문자열 폭발

 

어떻게 풀 것인가?

문제를 읽어보자.

예제 1에서 

"mirkovC4nizCC44" 이라는 문자열에 "C4"라는 문자열이 포함되어있으면 모두 없애야 한다. 케이스로 살펴보자.

 

Case 1 : mirkovC4nizCC44 => mirkovnizCC44 

 

Case 2 : mirkovnizCC44 => mirkovnizC4

 

Case 3 : mirkovnizC4 => mirkovniz(정답)

 

여기서 단, replaceAll() 이라는 메서드를 사용하게 되면, 문제에서 주어진 문자열의 최대 길이가 100만이기 때문에 반드시 메모리 초과가 날 것 이다. 그렇기에 스택을 활용하여 폭발 문자열과 일치하는 문자열을 그때 그때 바로 빼주는 식으로 다루면 메모리를 효율적으로 다룰 수 있다.

 

풀면서 놓쳤던점

맨 처음에 다소 문자열에 대해서 접근이 약해서 당황했고, 자료구조보단 알고리즘 위주로 생각을 많이했던 것 같다.

 

이 문제를 통해 얻어갈 것

스택의 활용

 

내 코드 

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

// 백준알고리즘 9935번 문자열 폭발
public class Main {
    static String N;
    static Stack<Character> st;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = br.readLine();
        String Boom = br.readLine();
        st = new Stack<>();

        for (int i = 0; i < N.length(); i++) {
            st.push(N.charAt(i));

            // 폭발 문자열과 길이가 같아지면 탐색 시작
            if (st.size() >= Boom.length()) {
                boolean flag = true;

                // st.size-regexSize부터 ~ st.size까지 탐색하여 regex와 일치하면 제거
                for (int j = 0; j < Boom.length(); j++) {
                    if (st.get(st.size() - Boom.length() + j) != Boom.charAt(j)) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    for (int j = 0; j < Boom.length(); j++) {
                        st.pop();
                    }
                }
            }

        }

        StringBuilder sb = new StringBuilder();
        for (Character c : st) {
            sb.append(c);
        }
        System.out.println(sb.length() == 0 ? "FRULA" : sb.toString());


    }
}

 

참고

X