[JAVA]문자열 폭발(Baekjoon)

문제

◾문제

 상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

 폭발은 다음과 같은 과정으로 진행된다.

• 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
• 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
• 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

 상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.

 폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

◾입력

 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.

 두 문자열은 모두 알파벳 소문자와 대문자, 숫자, 0, 1, …, 9로만 이루어져 있다.

◾출력

 첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.

예제 입력 1

mirkovC4nizCC44
C4

예제 출력 1

mirkovniz

예제 입력 2

12ab112ab2ab
12ab

예제 출력 2

FRULA

 처음 문제를 접했을 때, 단순히 문자열 내에서 폭발 문자열이 탐색되면 버퍼에 나머지 문자열을 저장, 폭발 문자열 만큼의 문자를 자르고 버퍼에 저장된 문자열을 다시 붙이면 된다는 생각을 했다.

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();     //입력 문자열
        String bomb = br.readLine();    //폭발 문자열
        String dump;                    //나머지 문자열 버퍼
        int tmp;

        //문자열 내에 폭발 문자열이 없을 때까지 반복
        while((tmp = str.indexOf(bomb)) != -1){
            dump = str.substring(tmp + bomb.length());  //나머지 문자열 저장

            //문자열 중간 이후에 폭발 문자열 있을 경우
            if(tmp != 0){
                str = str.substring(0, tmp);
                str = str.concat(dump);                 //나머지 문자열 붙이기
            }
            //문자열 처음에 폭발 문자열 있을 경우
            else
                str = str.substring(bomb.length());
        }

        if(str.length() == 0)       //문자열 길이가 0인 경우(모두 폭발)
            System.out.println("FRULA");
        else
            System.out.println(str);
    }
}

 위와 같이 풀어서 답은 나오지만, 메모리 초과가 발생했다.

 String 변수 3개와 int 변수 하나를 사용하는데 메모리 초과? 이해가 되지 않았다. 고심을 하다가 구글링을 했다.

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();         //입력 문자열
        String bomb = br.readLine();        //폭발 문자열
        int bomb_length = bomb.length();
        boolean isSame;
        Stack<Character> stk = new Stack<>();

        for(int i = 0; i < str.length(); i++){
            //스택에 문자 하나씩 push
            stk.push(str.charAt(i));
            if(stk.size() >= bomb_length){
                isSame = true;
                for(int idx = 0; idx < bomb_length; idx++){
                    //문자 하나씩 폭발 문자열 길이만큼 비교
                    if(stk.get(stk.size() - bomb_length + idx) != bomb.charAt(idx)){
                        isSame = false;
                        break;
                    }
                }
                //폭발 문자열과 동일한 문자열 발견 시
                if(isSame){
                    for(int j = 0; j < bomb_length; j++){
                        stk.pop();
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        if(stk.size() == 0)
            System.out.println("FRULA");
        else{
            for(Character c : stk){
                sb.append(c);
            }
            System.out.println(sb);
        }
    }
}

 위에서 내가 풀었던 방법은 String클래스에서 제공하는 indexOf, subString, concat 메소드를 사용하고, 아래의 방법은 charAt 메소드와 Stack 자료구조를 사용하는 것이 차이점이다.

 메모리 초과가 뜬 원인을 분석하기 위해 두 알고리즘이 사용한 메모리를 대략적으로 파악해보고자 했다.

분류	변수 × 개수
첫번째 방법	String × 3, int × 1
두번째 방법	String × 2, int × 1, Stack × 1, boolean × 1

 두번째 방법이 메모리 초과가 되지 않는다는 것은 String 변수 1개가 Stack + boolean 구조체보다 메모리를 많이 차지한다는 것이 된다. 따라서, String, Stack의 정의를 살펴보았다.

 Stack클래스는 Vector클래스를 상속받는데, Vector클래스는 Object의 리스트, int 타입의 카운트, 증가값을 가진다.

 String클래스는 byte의 리스트, byte타입의 coder변수, int타입의 hash변수, boolean타입의 변수를 2개 가진다.

 정의만 놓고 보았을때는 두 클래스의 대소비교를 하기에는 어렵다고 판단되었다.

 하지만 다시 생각해보았을때, 본 알고리즘에서의 차이가 있었다.

 첫번째 알고리즘의 경우, 입력문자열에서 폭발 문자열을 탐색하고나면 이후의 나머지 문자열을 모두 String변수에 할당한다. 이랬을때, 최악의 경우에는 "입력 문자열 길이 - 폭발 문자열 길이"만큼의 크기를 가지는 문자열이 할당이 되는데 이 경우에 사이즈가 매우 크다.

 동일한 테스트케이스일때를 가정하여 두번째 알고리즘을 고려해보자. Stack에 입력문자열의 처음부터 하나의 문자씩 push를 하기에 Stack의 사이즈는 "현재까지 탐색한 문자열의 크기 - 폭발문자열의 길이"가 된다. 그리고, 두번째 알고리즘의 최악의 경우(메모리 크기가 최대가 될 경우)를 생각해보면 정답일 경우에 메모리 크기가 최대가 된다.

◾결론

 같은 자료구조 혹은 비슷한 크기의 자료구조를 사용하더라도 알고리즘에 따라서 사용하는 메모리 크기가 상이하다. 이를 고려해서 알고리즘을 설계하도록 하자!