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

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

9935번: 문자열 폭발

 

 

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

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

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

 

상위권 사람들의 코드를 보니 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();
    }
}