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

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

 

 

문제 분석

• 문자열과 폭발 문자열을 입력받는다. 문자열에 존재하는 모든 폭발 문자열을 제거한 문자열을 반환한다.
• 문자열을 구셩하는 문자들을 하나씩 스택에 넣고, 폭발 문자열과 길이가 같아지는 지점부터 반복문을 통해 스택에 담긴 문자를 인덱스로 접근하여 검사한다.
  • (스택 사이즈) - (폭발 문자열 길이) + i (i는 0부터 시작하며 폭발 문자열의 길이이다.)
  • 검사 중 문자 하나라도 일치하지 않는다면 boolean 변수로 기록한 후 반복문을 빠져나온다.
• 스택에 폭발 문자열이 존재함이 증명된다면 poll을 통해 Stack에서 제거한다.
  👉 스택은 역으로 데이터 삭제가 가능하므로, 폭발 문자열 길이만큼 poll 하면 된다.
• 원본 문자열에 대한 검사가 끝나면 스택에 담긴 문자열을 출력한다.
  • 이때, Stack 사이즈만큼 반복하면서 poll을 하면 안 된다! poll을 하면 Stack의 사이즈가 줄어든다.

 

문제 풀이

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 br = new BufferedReader(new InputStreamReader(System.in));
        String origin = br.readLine(); // 문자열
        String explosives = br.readLine(); // 폭발 문자열

        Stack<Character> st = new Stack<>();

        for (int i = 0; i < origin.length(); i++) {

            // 원본 문자열을 하나씩 스택에 넣는다
            st.add(origin.charAt(i));//hilovehello -> love
            // 스택의 길이가 폭발 문자열의 길이 이상이 될 경우
            if (st.size() >= explosives.length()) {
                // 폭발 문자열을 포함하는지 검사한다
                boolean check = true;
                for (int j = 0; j < explosives.length(); j++) {
                    if (st.get(st.size() - explosives.length() + j) != explosives.charAt(j)) {
                        check = false;
                        break;
                    }
                }

                // 폭발 문자열을 포함한다면 스택에서 제거한다
                if (check) {
                    for (int j = 0; j < explosives.length(); j++) {
                        st.pop();
                    }
                }
            }
        }

        //Stack에 담긴 문자열을 출력한다
        StringBuilder sb = new StringBuilder();
        
        if (st.isEmpty()) System.out.println("FRULA");
        else {
            for (Character character : st)
                sb.append(character);
            System.out.println(sb);
        }
    }
}