[Baekjoon] 백준 9935: 문자열 폭발 - Java

문제

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

 

풀이

스택에 저장되어 있는 데이터에 대한 인덱스 접근을 해야 하는 문제이다. 필자는 Stack에 get(인덱스) 연산이 되는 것을 이 문제를 풀면서 알게 되었다.

 

스택에서 인덱스 접근이 왜 될까? 그 이유는 Stack은 Vector 기반으로 되어 있어 존재한다.

 

풀이 방식은 간단하다.

1. 문자열에 있는 문자를 스택에 넣는다.

2. 폭발하는 문자열의 끝 문자와 스택의 peek() 맨 위의 문자가 같으면서, 폭발하는 문자열 길이 이상만큼 스택에 문자가 저장되어 있다면, 시작 인덱스를 구하고, 스택의 문자와 폭발하는 문자열을 비교해 문자열이 폭발할 수 있는지(flag) 기록한다.

3. 폭발하는 문자열이면 스택에서 폭발하는 문자열 길이만큼 뺀다. 

 

소스코드

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

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<Character> stack = new Stack<>();
        
        for(int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            
            //일단 스택에 넣어봄
            stack.push(ch);
            
            //스택의 제일 끝 문자와 폭발 문자열의 끝 문자가 같고, 스택의 폭탄 문자열보다 더 많이 들어가 있다면,
            if (stack.peek() == bomb.charAt(bomb.length() - 1) && stack.size() >= bomb.length()) {
                //폭발 문자열 여부
                boolean flag = true;
                
                //stack에서의 시작 인덱스
                int startIdx = stack.size() - bomb.length();
                
                //폭발 문자열 크기 만큼 비교,
                for (int j = 0; j < bomb.length(); j++) {
                    if (bomb.charAt(j) != stack.get(j + startIdx)) {
                        flag = false;
                        break;
                    }
                }
                
                //폭발 문자열이라면, 폭발 문자열의 크기 만큼 뺀다.
                if (flag) {
                    int length = bomb.length();
                    
                    while (length > 0) {
                        stack.pop();
                        
                        length -= 1;
                    }
                }
            }
        }
        
        //스택이 비어 있다면,
        if (stack.isEmpty()) {
            System.out.print("FRULA");
            return;
        }
        
        StringBuilder sb = new StringBuilder();
        
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        
        System.out.print(sb.reverse());
        
        br.close();
    }
}