[백준_9935번] 문자열 폭발

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

9935번: 문자열 폭발

[문제]

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

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

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

 

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

 

[입력 조건]

• 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.
• 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.
• 두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.

 

[코드]

import java.util.*;

public class BaekJoon_9935 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		String str=sc.next();
		String boom=sc.next();
		Stack<Character> stack=new Stack<>();
		
		for(int i=0;i<str.length();i++) {
			stack.add(str.charAt(i));
			
			// 스택에 쌓인 문자의 갯수가 폭발 문자열의 길이와 같거나 클때 폭발 문자열이 있는지 검사
			if(stack.size()>=boom.length()) { 
				boolean flag=true; // 폭발 문자열이 포함되어 있는지 체크하는 변수
				// 스택에 있는 문자열과 폭발 문자열을 비교한다. 
				for(int j=0;j<boom.length();j++) {
					if(stack.get(stack.size()-boom.length()+j)!=boom.charAt(j)) {
						flag=false;
						break;
					}
				}
				if(flag) { // 폭발 문자열이 있다면 그 길이만큼 스택에서 제거해주기
					for(int j=0;j<boom.length();j++)
						stack.pop();
				}
			}
			
		}
		
		StringBuilder sb=new StringBuilder();
		for(char ch:stack)
			sb.append(ch);
		
		System.out.println(sb.length()>0?sb:"FRULA");
	}

}

 

[고찰]

 이번 문제의 핵심은 자료구조 스택을 사용해야 한다는 점이었다. 스택에 문자열을 삽입하면서 폭발 문자열의 길이만큼 문자가 쌓이면 스택에 쌓인 문자와 폭발 문자열을 비교하면서 폭발 문자열이 포함되어 있는지 확인하는 방식으로 해결할 수 있었다. 스택을 사용한다는 점만 파악했다면 쉽게 해결할 수 있는 문제였다.