[BOJ/Java] 9935. 문자열 폭발

[BOJ/Java] 9935. 문자열 폭발

9935번: 문자열 폭발

---

문제 해석

"문자열 폭발" 문제는 주어진 문자열에서 특정 "폭발 문자열"이 있을 경우, 그 문자열을 모두 제거하고, 제거 후 남은 문자열에 다시 폭발 문자열이 포함되어 있다면 이를 반복적으로 제거하는 과정을 거쳐 최종적으로 남은 문자열을 반환하는 문제다. 만약 모든 문자가 제거될 경우 "FRULA"를 출력한다. 이 문제는 특히 문자열 처리와 스택을 활용하는 알고리즘 설계 능력을 요구한다.

풀이 과정

이 문제를 해결하기 위해 스택을 활용하는 방법을 채택했다. 스택을 사용하는 이유는 문자열의 폭발이 발생할 때 효율적으로 문자를 제거하기 위해서이다. 다음과 같은 절차로 문제를 해결한다:

 

1. 입력받은 문자열을 순회하면서 각 문자를 스택에 쌓는다.
2. 새로운 문자가 스택에 추가될 때마다, 스택의 크기가 폭발 문자열의 길이 이상인지 확인한다.
3. 스택의 크기가 폭발 문자열의 길이 이상일 경우, 스택의 최근 문자들과 폭발 문자열을 비교한다.
4. 폭발 문자열과 일치하면 해당 문자들을 스택에서 제거한다.
5. 모든 문자를 처리한 후, 스택에 남은 문자들을 문자열로 변환하여 반환한다.
6. 스택이 비어있으면 "FRULA"를 출력한다.

 

이 과정에서 스택을 사용하면 각 문자의 추가 및 제거가 O(1) 시간에 이루어져서 전체적인 시간 복잡도를 효율적으로 관리할 수 있다.

코드

package edu.ssafy.im.BOJ.Gold.G4.No9935;

import java.io.*;
import java.util.Stack;

public class Main {
    private static char[] s;
    private static char[] b;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        s = br.readLine().toCharArray();  // 입력받은 문자열을 문자 배열로 변환
        b = br.readLine().toCharArray();  // 폭발 문자열을 문자 배열로 변환

        sb.append(sol());  // 처리 결과를 StringBuilder에 추가
        bw.write(sb.toString());  // 결과를 출력
        bw.flush();
        bw.close();
    }

    private static String sol() {
        Stack<Character> stack = new Stack<>();

        for (char c : s) {
            stack.push(c);  // 문자를 하나씩 스택에 쌓는다

            if (stack.size() < b.length) continue;  // 스택의 크기가 폭발 문자열보다 작으면 다음 문자 처리

            // 폭발 문자열과 스택의 최근 문자들을 비교
            boolean flag = true;
            for (int j = 0; j < b.length; j++) {
                if (stack.get(stack.size() - b.length + j) != b[j]) {
                    flag = false;  // 하나라도 다르면 폭발하지 않음
                    break;
                }
            }

            // 폭발 문자열이면 해당 문자들을 스택에서 제거
            if (flag) for (char t : b) stack.pop();
        }

        StringBuilder sb = new StringBuilder();
        for(char c : stack) sb.append(c);  // 스택에 남은 문자를 StringBuilder에 추가
        return stack.isEmpty() ? "FRULA" : sb.toString();  // 결과 문자열 반환
    }
}

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 주로 문자열 s를 순회하는 O(N)과 각 문자에 대해 최대 폭발 문자열 길이만큼 비교하는 O(M)의 곱, 즉 O(N*M)이 된다. 여기서 N은 입력 문자열의 길이이고, M은 폭발 문자열의 길이이다. 그러나 스택의 효율적인 사용으로 불필요한 반복을 줄이고 있어 실제 성능은 이보다 좋을 수 있다.

느낀점

스택을 활용하여 문자열 폭발 문제를 풀이하는 방법은 문자열 조작과 관련된 다양한 문제에 응용할 수 있는 효율적인 접근 방식을 제공한다. 이 문제를 통해 문자열 처리 기술과 자료 구조를 사용하여 문제를 해결하는 능력을 향상시킬 수 있었다.