[백준/Gold 4] 9934번 문자열 폭발 - Java, 자바

승래·2025년 9월 26일

9934번 문자열 폭발

문제 설명

https://www.acmicpc.net/problem/9935

문제

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

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

문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.
상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.

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

입력

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

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

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

출력

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

예제 입력

mirkovC4nizCC44
C4

예제 출력

mirkovniz

요구사항

주어진 문자열에 '폭발 문자열'이 존재한다면 제거하는 과정을 반복하는 문제이다. 규칙은 다음과 같다.

폭발: 문자열에 폭발 문자열이 포함된다면, 폭발 문자열을 제거한다.
재조합: 폭발 후 남은 문자열을 순서대로 재조합한다.
연쇄 폭발: 재조합된 문자열에 또 다시 폭발이 일어날 수 있다.
결과: 모든 폭발이 발생한 후 남은 문자열을 출력한다. 만약, 문자열이 모두 사라졌다면 "FRULA"를 출력한다.
제한: 문자열 길이가 최대 1,000,000이다.

접근 방식

문자의 최대 길이가 1,000,000이므로 여러번 순회하는 코드를 구현하면 매우 비효율적이라 시간 초과가 발생할 것이라고 생각했다.

따라서, 한번의 순회로 결과를 도출해내는 알고리즘이 필요했고, '스택'의 원리가 딱 들어맞았다.

결과 문자열을 만들어가는 과정을 스택에 문자를 쌓는데, 저는 StringBuilder가 문자열 처리에 더 효과적이라고 생각하여 스택을 생략하였다.

결과를 담을 StringBuilder를 생성한다.
입력 문자열을 처음부터 끝까지 순회하여 한 문자씩 append() 한다.(스택의 push)
append() 직후 마지막 부분이 폭발 문자열과 일치하는지 확인한다.
만약 일치한다면, 일치하는 부분만큼 delete()한다.(스택의 pop())
위와 같은 과정을 반복한다.

이 방식의 장점은 문자열 전체를 계속해서 다시 스캔할 필요없이, 새로 추가된 문자로부터 파생될 수 있는 폭발 가능성만 확인하면 되므로 매우 효율적인 알고리즘이다.

코드

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


public class Main{
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st;
      String line = br.readLine();
      String pat = br.readLine();
      StringBuilder sb = new StringBuilder();
      for(int i=0; i<line.length(); i++){
          sb.append(line.charAt(i));

          if(sb.length() >= pat.length()){
              String mat = sb.substring(sb.length() - pat.length()).toString();
              if(mat.equals(pat)){
                  sb.delete(sb.length() - pat.length(), sb.length());
              }
          }
      }
      String answer = sb.toString();
      if(answer.isEmpty()){
          System.out.println("FRULA");
      }
      else {
          System.out.println(answer);
      }
  }
}