[BAEKJOON] 9935. 문자열 폭발(JAVA)

:D 문제

---

문제

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

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

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

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

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

입력

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

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

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

출력

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

Baekjoon

9935번: 문자열 폭발

 

:D 풀이 방법

---

처음에는 단순 문자열 문제라 생각하여, 정규표현식과 replace메서드를 이용해 도전했다. 이 방법으로 풀이를 하면 메모리 초과가 발생하게 된다.(그 이유는 String 자료형은 불변 클래스(immutable class)이기 때문이다.)

 

그래서 1)StringBuilder와 2)Stack을 이용해 문제를 풀었다.

 

StringBuilder

1. 입력 문자열을 char[]로 저장한다.
2. 저장한 문자 배열을 하나씩 꺼내 answer에 추가한다.
3. 현재 answer의 길이가 target(폭발 문자열)보다 같거나 길다면, target이 포함되어 있는지 확인한다.
4. target이 포함되어 있다면, 제거한다.
   • 시작 index: (현재까지 추가한 문자열 길이  - target의 문자열 길이)
   • 끝 index : target 문자열 길이

Stack

   1 ~ 3. 위와 같이 1-3번의 순서를 거쳐 target(폭발 문자열)이 입력에 포함되어 있는지 확인한다.

   4. target(폭발 문자열) 길이만큼 pop()하여 제거한다.

 

:D 작성 코드

---

 

1) StringBuilder를 이용한 풀이

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

public class Main {

    public static void main(String[] args) throws IOException {

        // 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder answer = new StringBuilder();
        char[] input = br.readLine().toCharArray();
        String target = br.readLine();

        // 문자열 길이만큼 반복
        for (int i = 0; i < input.length; i++) {

            // 문자열 추가
            answer.append(input[i]);

            // 폭발 문자열보다 스택에 추가된 문자열이 더 긴 경우
            // 폭발 문자열이 포함될 수 있음
            if (target.length() <= answer.length()) {

                // 폭발 문자열 포함 여부
                boolean isContain = true;

                // 폭발 문자열 길이만큼 반복
                for (int j = 0; j < target.length(); j++) {
                    if (answer.charAt(answer.length() - target.length() + j) != target.charAt(j)) {
                        isContain = false;
                        break;
                    }
                }

                // 폭발 문자열이 포함되어 있다면 제거
                if (isContain) {
                   answer.delete(answer.length() - target.length(), answer.length());
                }
            }

        }

        // 출력
        if(answer.length() == 0) answer.append("FRULA");
        System.out.println(answer);
    }
}

 

2) Stack을 이용한 풀이 

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

public class Main {

    // 문자를 저장할 자료구조
    static Stack<Character> stack;

    public static void main(String[] args) throws IOException {

        // 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder answer = new StringBuilder();
        char[] input = br.readLine().toCharArray();
        String target = br.readLine();
        stack = new Stack<>();

        // 문자열 길이만큼 반복
        for (int i = 0; i < input.length; i++) {

            // 문자열 추가
            stack.push(input[i]);

            // 폭발 문자열보다 스택에 추가된 문자열이 더 긴 경우
            // 폭발 문자열이 포함될 수 있음
            if (target.length() <= stack.size()) {

                // 폭발 문자열 포함 여부
                boolean isContain = true;

                // 폭발 문자열 길이만큼 반복
                for (int j = 0; j < target.length(); j++) {
                    if (stack.get(stack.size() - target.length() + j) != target.charAt(j)) {
                        isContain = false;
                        break;
                    }
                }

                // 폭발 문자열이 포함되어 있다면 제거
                if (isContain) {
                    for (int j = 0; j < target.length(); j++) {
                        stack.pop();
                    }
                }
            }

        }

        // 출력
        if(stack.isEmpty()) answer.append("FRULA");
        else {
            for(char character : stack) {
                answer.append(character);
            }
        }
        System.out.println(answer);
    }
}

 

마무리

하나의 문제에도 다양하게 접근할 수 있게 방법을 고민해봐야겠다~!~!