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

문제 출처 - Baekjoon Online Judge

문제는 여기

9935번: 문자열 폭발

[문제] 

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

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

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

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

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

[입력]

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

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

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

[출력]

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

 

 

---

[풀이]

1. 입력 받은 문자열을 문자로 나눠 Stack에 넣어준다.

2. Stack의 크기가 폭발 문자열의 길이보다 길다면 폭발 문자열이 존재할 수 있으므로 탐색을 한다.

3. 스택에서 폭발 문자열과 비교를 해 다르다면 넘어간다.

4. 만약 폭발 문자열과 같다면 해당 문자들을 pop 해준다.

[접근]

1. contains를 사용해 폭발 문자열이 있다면 ""으로 변경해 반복을 돌리다 폭발 문자열이 존재하지 않거나 문자열의 길이가 짧아지면 탈출하도록 하려고 했다.

2. 위 방법으로 하니 메모리 초과가 발생하였다.

3. Stack을 사용해 문자열을 문자로 쪼개서 넣은 후 체크해서 폭발 문자열을 제거해주는 방법을 사용하였다.

[코드]

문자열 - 메모리 초과

package BOJ_gold;

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

public class Main_G4_9935_fail_memory {
	static String str;
	static String boom;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		str = br.readLine();
		boom = br.readLine();
		
		while (true) {
			if (str.length() == 0) {
				System.out.println("FRULA");
				System.exit(0);
			}
			
			if (!str.contains(boom)) {
				break;
			}
			else
				str = str.replace(boom, "");
		}
		
		System.out.println(str);
	}
}

stack - 정답

package BOJ_gold;

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

public class Main_G4_9935_stack {
	static String str;
	static String boom;
	static Stack<Character> st;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		str = br.readLine();
		boom = br.readLine();
		
		st = new Stack<>();
		
		for(int i = 0; i < str.length(); i++) {
			// 입력받은 문자열에서 알파벳으로 나눠서 스택에 넣기
			st.push(str.charAt(i));
			
			// 스택의 사이즈가 폭발 문자열의 길이보다 길다면
			// 폭발 문자열이 존재할 수 있다.
			if(st.size() >= boom.length()) {
				boolean contain = true; // 폭발 문자열이 있는지를 체크하기 위한 변수
				
				// 폭발 문자열의 길이만큼 반복
				for(int j = 0; j < boom.length(); j++) {
					// 스택의 길이 - 폭발 문자열의 길이를 빼고 거기서 부터 시작
					// 폭발 문자열과 다르면 탈출
					if(st.get(st.size() - boom.length() + j) != boom.charAt(j)) {
						contain = false;
						break;
					}
				}
				if (contain) {
					for(int j = 0; j < boom.length(); j++) {
						st.pop();
					}
				}
			}
		}
		
		// 쪼개져있는 문자들을 문자열로 만들어주기
		StringBuilder sb = new StringBuilder();
		for(Character c : st) {
			sb.append(c);
		}
		
		// 문자열의 길이가 0이라면 FRULA 출력, 아니라면 문자열 출력
		System.out.println(sb.length() == 0? "FRULA" : sb.toString());
	}
}