[백준 / 골드4] 9935 문자열 폭발 (Java)

문제 보기

사용한 것

• 문자를 추가시키다 조건이 일치하면 폭발시키기 위한 Stack

풀이 방법

• 입력 받은 str의 문자를 하나씩 stack에 넣는다.
• stack의 크기가 key의 크기보다 커지면 터질 수 있는지 탐색한다.
• 탐색 시에는 역순으로 두 문자열이 일치하는지 확인한다.
• pop()하면 문자열이 역순으로 출력되기 때문에 reverse()를 사용한다. (Deque 사용 시 필요 X)

코드

public class Main {

    private static String str;
    private static String explosionStr;

    public static void main(String[] args) throws IOException {
        init();
        print(getExplodedStr());
    }

    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        str = br.readLine();
        explosionStr = br.readLine();
        br.close();
    }

    private static String getExplodedStr() {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            stack.push(c);
            if (stack.size() >= explosionStr.length()) {
                explode(stack);
            }
        }
        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }

    private static void explode(Stack<Character> stack) {
        Stack<Character> tmpStack = new Stack<>();
        boolean check = true;
        for (int i = 0; i < explosionStr.length(); i++) {
            if (stack.peek() != explosionStr.charAt(explosionStr.length() - i - 1)) {
                check = false;
                break;
            }
            tmpStack.push(stack.pop());
        }
        if (!check) {
            while (!tmpStack.isEmpty()) {
                stack.push(tmpStack.pop());
            }
        }
    }

    private static void print(String str) {
        System.out.println("".equals(str) ? "FRULA" : str);
    }
}