[BOJ] 백준 9935번 문자열 폭발 (Java)

#9935 문자열 폭발

난이도 : 골드 4

유형 : 자료구조 / 문자열 / 스택

9935번: 문자열 폭발

▸ 문제

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

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

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

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

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

▸ 입력

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

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

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

▸ 출력

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

 

문제 풀이  

문자열에서 폭발 문자열과 일치하는 문자열을 모두 제거해준다음 남은 문자열을 출력해주면 된다.

 

📚 조건

• 문자열 길이 line ( 1 <= line <= 1,000,000)
• 폭발 문자열 길이 regex ( 1 <= regex <= 36)

 

문자열의 최대길이가 100만이기 때문에 문자열 메소드 replaceAll을 사용하면 메모리초과가 발생한다.  스택을 활용하여 폭발 문자열과 일치하는 문자열을 그때그때 바로 빼주는 식으로 push와 pop연산이 이뤄지기 때문에 메모리를 효율적으로 다룰 수 있다.

 

구상

1. 문자열 line의 전체 길이를 탐색하여 스택에 push해준다.
2. 스택에 들어간 문자의 길이가 폭발 문자열의 길이보다 길다면 폭발 문자열이 있는지 탐색해준다. (st.size-regex.size ~ st.size)
   1. 일치하지 않는다면 break;
   2. 폭발 문자열과 일치하는 문자열이 있다면 st.pop();

 

풀이 코드 

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

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = br.readLine();
		String regex = br.readLine();
		int regexSize = regex.length();
		
		Stack<Character> st = new Stack<>();
		
		for(int i=0; i<line.length(); i++) {
			st.push(line.charAt(i));
			
			// 폭발 문자열과 길이가 같아지면 탐색 시작 
			if(st.size()>= regexSize) {
				boolean flag = true;
				
				// st.size-regexSize부터 ~ st.size까지 탐색하여 regex와 일치하면 제거 
				for(int j=0; j<regexSize; j++) {
					if(st.get(st.size()-regexSize+j) != regex.charAt(j)) {
						flag = false;
						break;
					}
				}
				if(flag) {
					for(int j=0; j<regexSize; j++) {
						st.pop();
					}
				}
			}
			
		}
		
		StringBuilder sb = new StringBuilder();
		for(Character c : st) {
			sb.append(c);
		}
		System.out.println(sb.length()==0? "FRULA" : sb.toString());
	}
}