[백준 9935/자바] 문자열 폭발

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

 

---

 

문자열의 최대길이가 100만이기 때문에 문자열 메소드 replaceAll을 사용하면 메모리초과가 발생한다고 한다...

 

✨ 참고
https://loosie.tistory.com/317

 

---

 

풀이

스택 사용

 

1. 스택에 입력받은 문자열을 한 글자씩 집어넣음
2. 스택의 크기가 폭발 문자열의 길이와 같거나 길이보다 클 경우 폭발 문자열이 포함 돼있는지 확인
3. 스택의 최상단에서 폭발 문자열 길이까지만 get 함수를 이용해 앞에서부터 차례대로 확인한다
4. 만약 폭발 문자열이 포함 돼있으면 그 길이만큼 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 br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        String str = br.readLine(); // 일반 문자열
        String bombStr = br.readLine();    // 폭발 문자열
        
        int bombLength = bombStr.length();  // 폭발 문자열 길이

        // 일반 문자열 저장할 스택
        Stack<Character> stack = new Stack<>();

        /**
         * 일반 문자열을 한 글자씩 스택에 입력
         * 스택 길이가 폭발 문자열 길이가 길거나 같을 때마다 폭발 문자열이 포함 돼있는지 확인
         * 
         * 1) 스택의 가장 뒤쪽에서부터, (폭발 문자열 길이)개의 문자 한 글자씩 확인
         * 2) 만약 같지 않은 문자가 한 글자라도 있으면 폭발 문자열 포함 X
         * 3) 폭발 문자열이 포함 돼있으면 스택에서 그 글자들을 pop한다
         */
        for (int i = 0; i < str.length(); i++) {
            stack.push(str.charAt(i));  // 한 글자씩 스택에 추가

            // 스택 길이가 폭발 문자열 길이보다 길거나 같을 경우
            if (stack.size() >= bombLength) {
                boolean flag = true;    // 폭발 문자열 포함 여부 저장

                for (int j = 0; j < bombLength; j++) {
                    /** 
                     * 한 글자씩 비교 후 한 글자라도 같이 않으면 포함 X
                     */
                    if (stack.get(stack.size() - bombLength + j) != bombStr.charAt(j)) {
                        flag = false;
                        break;
                    }
                }

                /**
                  * flag가 true인 것은 폭발 문자열이 포함된 것
                 * 그 문자열의 길이만큼 pop 실행
                  */
                if (flag) {
                    for (int j = 0; j < bombLength; j++) {
                        stack.pop();
                    }
                }
            }
        }

        // 남은 문자열 출력
        for (char s : stack) {
            sb.append(s);
        }

        // sb.isEmpty() 함수 사용 시 백준 사이트 내에서 컴파일 에러가 남
        System.out.println(sb.length() == 0 ? "FRULA" : sb);
    }

}