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

문제 링크:

9935번: 문자열 폭발

 

 

난이도: 골드 4

 

 

문제:

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

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

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

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

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

 

 

입력:

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

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

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

 

 

출력:

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

 

 

문제 이해:

이 문제는 문자열 처리 문제로, 주어진 문자열에서 특정 “폭발 문자열”이 나타날 때마다 즉시 제거하는 과정을 반복한 뒤 남은 문자열을 출력하는 것이다.

입력은 두 줄로 주어진다.

• 첫째 줄: 전체 문자열
• 둘째 줄: 폭발 문자열

즉, 첫 번째 문자열 안에 두 번째 문자열이 포함되어 있다면 그 부분을 모두 삭제하고, 삭제로 인해 새롭게 생긴 폭발 문자열도 계속해서 제거해야 한다.

 

예제 입력 1로 살펴보자.

 

입력:

mirkovC4nizCC44

C4

 

1단계

폭발 문자열 "C4" 발견 → 제거

남은 문자열: mirkovnizCC44

 

2단계

다시 폭발 문자열 "C4" 발견 → 제거

남은 문자열:mirkovnizC4

3단계

삭제로 인해 새롭게 생긴 "C4" 또 발견 → 제거

남은 문자열: mirkovniz

 

최종 결과: mirkovniz

 

 

구현 방향:

처음에 작성자는 이 문제가 왜 골드 난이도인지 이해가 가지 않았다.
입력한 문자열에 폭발 문자열이 포함되어 있다면, 단순히 다음과 같이 replace()를 이용해 제거하면 된다고 생각했기 때문이다.

while (str.contains(explosion)) {
    str = str.replace(explosion, "");
    if (str.equals("")) {
        flag = true;
    }
}

즉, 폭발 문자열이 포함되지 않을 때까지 계속 제거하고,
문자열이 완전히 비어 있다면 "FRULA"를 출력하는 간단한 방식이었다.

 

하지만 이 코드는 메모리 초과로 실패했다.
그 이유는 replace()가 문자열을 교체할 때마다 새로운 문자열 객체를 생성하기 때문이다.
한 번 문자열 전체를 탐색해서 교체했더라도, 다시 contains()로 전체를 재탐색해야 하므로
결국 문자열 길이가 길어질수록 시간 복잡도와 메모리 사용량이 폭증하게 된다.

 

작성자는 여러 자료를 찾아본 끝에, 스택(Stack) 을 활용한 효율적인 방법을 발견했다.
이 방식은 문자열을 앞에서부터 한 글자씩 스택에 넣으면서,
새로 넣은 문자로 인해 스택의 끝부분에 폭발 문자열이 완성되었는지 확인하고,
완성되었다면 즉시 그 부분을 제거하는 원리다.

이렇게 하면 전체 문자열을 단 한 번만 순회하면서 원하는 결과를 얻을 수 있다.
(시간 복잡도 O(N))

 

예제 입력 1로 예시를 들어보자

mirkovC4nizCC44
C4

 

과정:

1	push m	폭발 문자열 길이(2)보다 작음 → 검사 불필요	[m]
2	push i	길이 같지만 끝부분 "mi" ≠ "C4" → 검사 실패	[m, i]
3	push r	길이 > 2 → 끝부분 "ir" ≠ "C4" → 실패	[m, i, r]
4	push k	끝부분 "rk" ≠ "C4" → 실패	[m, i, r, k]
5	push o	끝부분 "ko" ≠ "C4" → 실패	[m, i, r, k, o]
6	push v	끝부분 "ov" ≠ "C4" → 실패	[m, i, r, k, o, v]
7	push C	끝부분 "vC" ≠ "C4" → 실패	[m, i, r, k, o, v, C]
8	push 4	끝부분 "C4" = 폭발 문자열 → 두 글자 제거	[m, i, r, k, o, v]
9	push n	끝부분 "vn" ≠ "C4" → 실패	[m, i, r, k, o, v, n]
10	push i	끝부분 "ni" ≠ "C4" → 실패	[m, i, r, k, o, v, n, i]
11	push z	끝부분 "iz" ≠ "C4" → 실패	[m, i, r, k, o, v, n, i, z]
12	push C	끝부분 "zC" ≠ "C4" → 실패	[m, i, r, k, o, v, n, i, z, C]
13	push C	끝부분 "CC" ≠ "C4" → 실패	[m, i, r, k, o, v, n, i, z, C, C]
14	push 4	끝부분 "C4" = 폭발 문자열 → 두 글자 제거	[m, i, r, k, o, v, n, i, z, C]
15	push 4	끝부분 "C4" = 폭발 문자열 → 두 글자 제거

 

이를 그대로 코드로 구현하면 다음과 같다.

 

 

정답 코드:

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

public class Main {
    static StringBuilder str; //입력 문자
    static StringBuilder explosion; // 입력 폭발 문자
    static int explosionSize;
    static Stack<Character> stack=new Stack<>();

    public static void solve() {
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            stack.add(c);

            // 스택 안에 요소가 폭발문자열 길이보다 작으면 검사 불필요
            if (stack.size() < explosionSize) continue;

            // 스택 끝 부분부터 폭발문자열 검사
            boolean match = true;
            for (int k = 0; k < explosionSize; k++) {
                if (stack.get(stack.size() - explosionSize + k) != explosion.charAt(k)) {
                    match = false;
                    break;
                }
            }

            // 폭발 문자열이면 제거
            if (match) {
                for (int j = 0; j < explosionSize; j++) {
                    stack.pop();
                }
            }
        }

        // 결과 출력
        if (stack.isEmpty()) System.out.println("FRULA");
        else {
            StringBuilder sb = new StringBuilder();
            for (char c : stack) {
                sb.append(c);
            }
            System.out.println(sb);
        }
    }

    public static void main(String[] args) throws IOException {
        //초기 세팅
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        String str1=br.readLine();
        str=new StringBuilder(str1);

        String str2= br.readLine();
        explosion=new StringBuilder(str2);
        explosionSize=explosion.length();
        //초기 세팅 끝

        //폭팔 시작
        solve();
    }
}

 

 

마무리하며:

이 문제는 개인적으로 좋은 문제라고는 생각하지 않는다.
그 이유는 단순히 문자열을 제거하는 문제처럼 보이지만,
str.replace()와 같은 내장 메서드의 내부 동작 원리를 이해하지 못하면
왜 시간 초과나 메모리 초과가 나는지 파악하기 어렵기 때문이다.

 

또한, while(true) 루프와 같이 언제 종료될지 컴파일러가 예측할 수 없는 반복문은
for문에 비해 JIT(Just-In-Time) 최적화가 이루어지지 않아
반복 횟수가 같더라도 실제 실행 속도에서 큰 차이를 낸다는 점도 배웠다.

 

이번 문제를 통해 단순히 알고리즘의 논리만이 아니라,
시간 복잡도와 메모리 사용량, 그리고
컴파일러 최적화와 CPU 관점의 성능 차이까지 고려하는 시야를 얻을 수 있었다.
앞으로는 문제를 풀 때 단순히 돌아가는 코드가 아니라
왜 빠른지, 왜 느린지를 함께 고민하며 코드를 작성해야겠다고 느꼈다.

 

 

감사합니다.