[백준] 9935번 문자열 폭발 (Java)
Algorithm/Baekjoon Online Judge

[백준] 9935번 문자열 폭발 (Java)

728x90

백준 9935번 문자열 폭발 : https://www.acmicpc.net/problem/9935

 

9935번: 문자열 폭발

문제 상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다. 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다. 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다. 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다. 상근이는 모든 폭발이 끝난

www.acmicpc.net

 

 

예전에 풀었던 키로거 문제에서 문자열 처리할 때 스택을 사용했던 기억이 나서 스택을 사용해서 구현했다.

문자열의 각각의 문자를 스택에 넣으면서 폭발물과 일치하는 부분이 생기면 스택에서 꺼내는 방식이었다.

이런 식으로 풀이를 하면 위의 결과처럼 메모리도 많이 먹고 시간이 오래 걸리게 된다.

 

상위권 사람들의 코드를 보니 char 배열을 사용해서 구현했더라.

스택을 사용하는 방식과 비슷하지만 char 배열의 index를 조작하며 배열에 저장하는 방식이었다.

스택을 사용하면 스택에서 꺼내는 로직이 필요하지만, 배열을 사용하면 삭제할 필요 없이 그 위에 저장해도 되서 시간이 단축된다.

String.valueOf 함수도 새롭게 알게 되었다.

 

 

총 걸린 시간 : 30분

난이도 : ★★☆☆☆

 

코드

char[] 사용 (216ms)

import java.io.BufferedReader;
import java.io.InputStreamReader;

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 answer = solution(str, bomb);
        System.out.println((answer.length() == 0) ? "FRULA" : answer);
    }

    private static String solution(String str, String bomb) {
        char[] result = new char[str.length()];
        int idx = 0;

        for (int i = 0; i < str.length(); i++) {
            result[idx] = str.charAt(i);
            if (isBomb(result, idx, bomb)) idx -= bomb.length();
            idx++;
        }

        return String.valueOf(result, 0, idx);
    }

    private static boolean isBomb(char[] result, int idx, String bomb) {
        if (idx < bomb.length() - 1) return false;

        for (int i = 0; i < bomb.length(); i++) {
            if (bomb.charAt(i) != result[idx - bomb.length() + 1 + i]) return false;
        }
        return true;
    }
}

 

Stack 사용 (464ms)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;

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 answer = solution(str, bomb);
        System.out.println((answer.length() == 0) ? "FRULA" : answer);
    }

    private static String solution(String str, String bomb) {
        Stack<Character> stack = new Stack<>();
        int blen = bomb.length();

        for (int i = 0; i < str.length(); i++) {
            stack.push(str.charAt(i));

            if (stack.size() >= blen) {
                boolean flag = true;
                for (int j = 0; j < blen; j++) {
                    if (stack.get(stack.size() - blen + j) != bomb.charAt(j)) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    for (int j = 0; j < blen; j++) {
                        stack.pop();
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (Character character : stack) {
            sb.append(character);
        }
        return sb.toString();
    }
}
728x90