[백준] 9935: 문자열 폭발 (Stack) - JAVA

class 4

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

 

 

 

 

# 문제

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

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

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

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

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

 

 

# 예제

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

mirkovC4nizCC44
C4

 

 

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

mirkovniz

 

 

# 필요개념

이 문제는 폭발 문자열을 제거하는 문제이다. 문자 한개씩 스택에 넣고, 스택의 peek()이 폭발문자열의 마지막 문자와 같으면 둘이 같은지 비교 후 같으면 제거하면 된다. 비교할 때에는 스택의 get 메소드를 사용했다.

 

이렇게 단순하게 풀면 OutOfIndexException이 발생한다. 문제를 잘 보면, 문자열의 길이가 폭발문자열의 길이보다 길다는 보장이 없다. 또,

str = ababab

bomb = acb 

인 경우, str의 첫 b에서 비교가 일어나는데, ab가 acb보다 짧기 때문에 OutOfIndex 에러가 발생하는 것이다. 

그래서 스택의 peek()이 폭발문자열의 마지막 문자와 같으면 둘이 같은지 비교함과 동시에 스택의 size가 bomb의 길이보다 같거나 큰지 여부도 확인해야 한다.

 

그래서 if문을 이렇게 작성하였다.

 

또, 만약 남은 문자열이 없다면 FRULA를 출력해야 한다는 것을 잘 봐두어야 한다! 이거 때문에 틀렸었다.

 

# Code

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 bomb = br.readLine();

        Stack<String> stk = new Stack<>();
        int idx = 0;
        StringBuilder sb = new StringBuilder();

        while (idx < str.length()) {
            String cur = String.valueOf(str.charAt(idx));
            boolean isBomb = true;
            stk.push(cur);
            idx++;
            if (stk.size() >= bomb.length() && stk.peek().equals(String.valueOf(bomb.charAt(bomb.length() - 1)))) {
                for (int i = 1 ; i <= bomb.length() ; i++) {
                    if (!stk.get(stk.size() - i).equals(String.valueOf(bomb.charAt(bomb.length() - i)))) {
                        isBomb = false;
                    }
                }
                if (isBomb) {
                    for (int i = 0 ; i < bomb.length() ; i++) {
                        stk.pop();
                    }
                }
            }
        }
        if (stk.isEmpty()) sb.append("FRULA");
        else {
            Stack<String> ans = new Stack<>();
            while (!stk.isEmpty()) {
                ans.push(stk.pop());
            }

            while (!ans.isEmpty()) {
                sb.append(ans.pop());
            }
        }
        System.out.println(sb.toString());
    }
}

 

# 결과