[백준] 9935 : 문자열 폭발

문제 출처: https://www.acmicpc.net/problem/9935

---

문제

---

시도

 

일단 무난하게 contains()로 확인하고 replace로 대체하는 식으로 작성했다.

 

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        String expl = br.readLine();

        while (str.contains(expl)) {
            str = str.replace(expl, "");
        }

        System.out.print(str.equals("") ? "FRULA" : str);
    }

}

 

43%까지 진행되다가 메모리 초과로 실패했다.

쉽게 날먹하려고 했는데 역시 골드는 골드였다.

---

풀이

 

다른 사람의 풀이를 참고하니 Stack을 통해 input을 char 단위로 하나씩 받아들여 폭탄 문자열의 길이보다 크거나 같을 때 비교를 수행하는 로직으로 풀었다.

 

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 line = br.readLine();
        String regex = br.readLine();
        int regSize = regex.length();

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

        for (int i = 0; i < line.length(); i++) {
            st.push(line.charAt(i));

            if (st.size() >= regSize) {
                boolean flag = true;

                // st.size - regSize 부터 st.size까지 탐색하여 regex와 일치하면 제거
                for (int j = 0; j < regSize; j++) {
                    if (st.get(st.size() - regSize + j) != regex.charAt(j)) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    for (int j = 0; j < regSize; j++) {
                        st.pop();
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for(Character c : st) {
            sb.append(c);
        }

        System.out.print(sb.length() == 0 ? "FRULA" : sb.toString());
    }
}

 

 

풀이 참고: https://loosie.tistory.com/317

---

알게 된 점

 

기존 시도 코드에서 메모리 초과가 발생했던 이유는 기존 문자열의 내용을 바꾸는 replace() 메서드에 의한 것이었다.

 

문자열은 불변(immutable)한 객체이기 때문에 `str.replace(expl, "")` 메서드는 새로운 문자열을 생성하는데, 만약 입력 문자열이 매우 큰 경우(최대 1,000,000), 반복적으로 새로운 문자열을 생성하는 작업이 메모리를 소모하게 되어 메모리 초과가 발생한 것이었다.

(※ 이는 제거하려는 expl 문자열의 길이가 길 경우에도 해당하지만 문제에서 expl의 최대 길이는 36이라고 명시되어 해당되진 않았다.)