[백준_JAVA_알고리즘] 9935 문자열 폭발 #스택

 

다음 문제는 스택을 이용해서 해결할 수 있습니다.

스택은 LIFO 원칙에 따라 데이터를 저장합니다. 따라서 pop()을 통해 최근에 추가된 문자들을 빠르게 제거할 수 있습니다. 또한, 폭발 문자열을 제거한 후에도 나머지 문자들의 순서가 보장됩니다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();
        Stack<Character> stack = new Stack<>();

        String str = bufferedReader.readLine(); // 문자열
        String bomb = bufferedReader.readLine(); // 폭발 문자열

        for (int i = 0; i < str.length(); i++) {
            stack.push(str.charAt(i));

            if (stack.size() >= bomb.length()) {
                boolean isBomb = true; // 폭발 문자열 있음

                for(int j = 0; j < bomb.length(); j++){
                    if(stack.get(stack.size() - bomb.length() + j) != bomb.charAt(j)){
                        isBomb = false;
                        break;
                    }
                }

                if(isBomb){
                    for(int k = 0; k < bomb.length(); k++){
                        stack.pop();
                    }
                }
            }
        }

        if(stack.isEmpty())
            System.out.println("FRULA");
        else{
            for(char c: stack)
                stringBuilder.append(c);
        }
        System.out.print(stringBuilder);
    }
}

 

먼저 문자열의 각 문자를 순서대로 스택에 추가합니다.

스택의 크기가 폭발 문자열의 길이보다 크거나 같을 때만 검사를 시작합니다.

가장 최근의 문자들이 폭발 문자열과 일치하면 boolean isBomb = true;로 설정합니다. 만약 다르다면 false로 설정하고 종료합니다.

pop() 연산을 통해 폭발 문자열을 제거합니다.

StringBuilder에 문자들을 순서대로 추가하여 출력합니다.

 

.

.

.

 

문제는 아래에서 확인할 수 있습니다.

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