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

0. 출처

백준 9935번 문제입니다.

 

1. 문제

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

• 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
• 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
• 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

(1) 입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.

(2) 출력

첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.

 

2. 문제 풀이

(1) 문제 풀이 방법

가장 먼저 떠오른 방법은 replaceAll()을 사용하는 것이였습니다. 머릿 속에서 생각한 풀이를 코드로 옮겨보자면..

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        String target = br.readLine();  

        while(str.contains(target)) {
            str = str.replaceAll(target, "");
        }

        if(str.length() == 0) {
            System.out.println("FRULA");
        } else {
            System.out.println(str);    
        }
        br.close();
    }
}

 

그러나 contains()와 replaceAll()의 시간 복잡도는 둘 다 O(nm)이기 떄문에 이 코드는 시간 초과가 발생합니다. (n은 str의 길이, m은 찾고자 하는 target의 길이) 그럼 어떤 방법이 있을까요?

 

Stack을 활용해서 찾는 문자열이 있을 때마다 폭발을 시키며 지나가는 것이 효율적인 풀이 방법이 될 것 입니다. 

 

1. 문자를 stack에 넣는다.
2. 만약 stack의 size가 target의 길이보다 크거나 같다면 stack에 들어있는 문자를 target과 비교한다.
3. 만약 같으면 stack에서 pop()한다.

(2) 코드 (Java)

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        String target = br.readLine();  

        Stack<Character> st = new Stack<>();
        
        for(int i=0; i<str.length(); i++) {
            st.push(str.charAt(i)); // 1. 문자를 stack에 넣는다.

            if(st.size()>=target.length()) { // 2. 만약 stack의 size가 target의 길이보다 크거나 같다면
                boolean flag = true;
                for(int j=0; j<target.length(); j++) { // stack에 들어있는 문자들을 target과 같은지 비교한다.
                    if(target.charAt(j) != st.get(st.size()-target.length()+j)) {
                        flag = false;
                        break;
                    }
                }
                if(flag) { // 3. 만약 같으면 stack에서 pop()한다.
                    for(int k=0; k<target.length(); k++) {
                        st.pop();
                    }
                }
            }
        }
		
		StringBuilder sb = new StringBuilder();
        if(st.isEmpty()) {
            sb.append("FRULA");
        } else {
            for(char c: st) {
                sb.append(c);
            }
        }

		System.out.println(sb.toString());
        br.close();
    }
}

 

(3) 결과