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

문제 9935

9935번: 문자열 폭발

[ 문제 풀이 ]

N의 길이가 1,000,000이므로 시간복잡도를 고려해야 합니다. O(N)의 시간복잡도를 가질 수 있도록 해야 하기 때문에 replaceAll()과 같은 함수는 사용할 수 없습니다.

문자열의 길이만큼 처음부터 순회하며 Stack에 하나씩 넣은 다음, 폭발 문자열의 길이보다 클 때 폭발 문자열의 길이만큼 반복하여 폭발 문자열과 같은 것이 있는지 확인합니다. 없을 경우 flag를 false로 바꾸고, 반복문을 break로 빠져나옵니다.

flag가 true이면 stack이 비어있을 때는 "FRULA"를 출력하도록 하고, stack이 비어있지 않다면 남아있는 문자열을 출력합니다.

[ 코드 ]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String str = br.readLine();
        String bomb = br.readLine();
        int bombSize = bomb.length();

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

            if (stack.size() >= bombSize) {
                boolean flag = true;
                for (int j = 0; j < bombSize; j++) {
                    if (stack.get(stack.size()-bombSize+j) != bomb.charAt(j)) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    for (int j = 0; j < bombSize; j++) {
                        stack.pop();
                    }
                }
            }
        }

        if (stack.isEmpty()) {
            bw.write("FRULA");
        } else {
            for (Character character : stack) {
                bw.write(character);
            }
        }
        bw.flush();
    }
}