[JAVA] 백준 9935 문자열 폭발

들어가며..

이전에 풀기에 실패했던 9935 문자열 폭발을 다시 풀어보았고 다시 실패해서 해결방법을 보고 작성한다.

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

본론

이전에 풀었던 방식은 replace 메서드를 사용한 방식으로 풀어보았었고, 오늘 다시 풀었을 때는, StringBuilder의 delete()를 활용해서 지워나갔지만, 여전히 메모리 초과가 발생했다

문제의 코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringBuilder value = new StringBuilder(br.readLine());
        String target = br.readLine();

        boolean isDelete = true;
        while (isDelete) {
            isDelete = false;

            for(int i=0; i<value.length() - target.length() + 1; i++){
                if(value.substring(i, i + target.length()).equals(target)){
                    value.delete(i, i + target.length());
                    isDelete = true;
                }
            }
        }

        System.out.println(value.length() == 0 ? "FRULA" : value);

    }
}

• 그래서 찾아보았더니 스택을 활용한 문제였다

설명

입력된 문자열을 0번 부터 시작하면서 stack에 담아준다.

만약 stack의 size가 target의 크기보다 크다면, 다음의 로직을 수행한다.

1. stack의 마지막에 존재하는 문자열(target 사이즈)이 target과 일치하는지 검사한다.
2. 만약 일치한다면, stack에서 일치하는 문자열을 pop() 하여 제거한다.

정말 간단했다.

예제

아래의 입력이 주어졌을 경우를 가정한다.

mirkovC4nizCC44
C4

i = 0

• stack [m]
• stack size = 1이기 때문에 로직이 동작하지 않는다.
• 결과 : [m]

i = 1

• stack [m, i]
• 이 경우 mi ≠ C4이기 때문에 삭제하지 않는다.
• 결과 : [m, i]

…. i = 8

• stack [m, i, r, k, o, v, C, 4]
• 이 경우 C4 = C4이기 때문에 마지막 2개를 pop()을 호출하여 삭제한다.
• 결과 : [m, i, r, k, o, v]

… i = 13

• stack [m, i, r, k, o, v, n, i, z, C, C, 4]
• 이 경우에도 C4 = C4이기 때문에 마지막 2개를 삭제한다.
• 결과 : [m, i, r, k, o, v, n, i, z, C]

i = 14

• stack [m, i, r, k, o, v, n, i, z, C, 4]
• 이 경우에도 마지막 2개를 삭제한다.

결과적으로 stack에는 다음의 값이 남게되고 답이 된다.

stack [m, i, r, k, o, v, n, i, z]

소스코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        Stack<Character> stack = new Stack<>();
        char[] value = br.readLine().toCharArray();
        char[] target = br.readLine().toCharArray();

        for(int i=0; i<value.length; i++){
            stack.push(value[i]);
            if(stack.size() >= target.length){
                boolean flag = true;

                for(int j=0; j<target.length; j++){
                    if(stack.get(stack.size() - target.length + j) != target[j]){
                        flag = false;
                        break;
                    }
                }

                if(flag){
                    for(int j=0; j<target.length; j++){
                        stack.pop();
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for(char v : stack){
            sb.append(v);
        }
        System.out.println(sb.length() == 0 ? "FRULA" : sb);
    }
}

알게된 점

• Stack 클래스의 메서드로 get()이 존재하는지 처음 알게되었다.