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

문제

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

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

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

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

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

입력

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

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

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

출력

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

---

풀이(틀린풀이)

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String long_str = br.readLine();
		String boom = br.readLine();

		ArrayList<Character> long_list = new ArrayList<Character>();

		for (int i = 0; i < long_str.length(); i++) {
			long_list.add(long_str.charAt(i));
		}

		for (int i = 0; i <= long_list.size() - boom.length(); i++) {
			boolean isBoom = false;
			if (long_list.get(i) == boom.charAt(0)) {
				isBoom = true;
				for (int j = 0; j < boom.length(); j++) {
					if (boom.charAt(j) != long_list.get(i + j)) {
						isBoom = false;
						break;
					}
				}
			}
			if (isBoom == true) {
				for (int j = 0; j < boom.length(); j++) {
					long_list.remove(i);
				}
				i -= boom.length();
				if (i < 0) {
					i = -1;
				}
			}
		}

		if (long_list.size() == 0) {
			System.out.print("FRULA");
		} else {
			for (char a : long_list) {
				System.out.print(a);
			}
		}
	}
}​

 

틀린풀이)

1. ArrayList에 문자열 추가

2. ArrayList를 순차탐색하며 Boom할 단어의 첫글자가 같은 글자를 탐색

2-1. Boom 단어와 비교

2-2. ArrayList.remove로 삭제 후 Boom할 단어의 size만큼 인덱스 전으로 돌린뒤 다시 탐색.

2-3. 반복

 

틀린풀이 결과)

시간초과 가 나왔다.

 

틀린풀이 분석)

ArrayList가 원인인 것 같았다.

문제 특성상 중간에 list.remove()를 많이 사용하는데, 이렇게 되면

출처 : https://seeminglyjs.tistory.com/204

다음과 같이 뒤에 있는 자료 모두 인덱싱 작업을 다시하게 된다.

이 작업을 수행하지 않는 LinkedList를 살펴보면

출처 : https://seeminglyjs.tistory.com/204

다음과 같이 다음 자료와 연결작업만 수행하면 되므로 뒤에 자료 인덱싱 작업을 하지않아 속도가 더 빠를 것이라고 예상하였다.

직접 코드에 적용시켜보았다.

...
//		ArrayList<Character> long_list = new ArrayList<Character>();
		LinkedList<Character> long_list = new LinkedList<Character>();
        
...

다음과 같이 ArrayList를 LinkedList로만 수정해도 기본적인 add, remove 작업은 함수가 공유되므로 편하게 변경할 수 있었다.

시간을 재보았다.

ArrayList와 LinkedList의 시간 차이

많은 시간차이가 난다.

 

이제 맞겠지?

 

......

결국 스택형식으로 새로 짯다.

---

풀이

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String str = br.readLine();
		String bomb = br.readLine();

		Stack<Character> stack1 = new Stack<Character>();
		Stack<Character> stack2 = new Stack<Character>();

		for (int i = 0; i < str.length(); i++) {
			stack1.push(str.charAt(i));
		}
		int idx = 0;
		while (!stack1.isEmpty()) {
			stack2.push(stack1.pop());
			if (stack2.peek() == bomb.charAt(bomb.length() - (idx + 1))) { // 폭발문자열과 문자가같으면
				idx++;
			} else {
				idx = 0;
				if (stack2.peek() == bomb.charAt(bomb.length() - (idx + 1))) { // 하나라도 다르면 초기화
					idx++;
				}
			}
			if (idx == bomb.length()) { // 폭발문자열이 나오면
				for (int i = 0; i < bomb.length(); i++) {
					stack2.pop(); // 길이만큼 빼주고
				}
				for (int i = 0; i < bomb.length(); i++) {
					if (!stack2.isEmpty()) {
						stack1.push(stack2.pop()); // 재검사를 위해 폭발문자열길이만큼 stack1에 다시푸쉬
					} else {
						break;
					}
				}
				idx = 0;
			}
		}
		if (stack2.isEmpty()) {
			System.out.println("FRULA");
		} else {
			StringBuilder sb = new StringBuilder();
			while (!stack2.isEmpty()) {
				sb.append(stack2.pop());
			}
			System.out.println(sb.toString());
		}
	}
}

스택 두개를 이용하였다.

1. stack1에 문자열을 입력받는다

2. stack2에 stack1에서 pop한것을 push한다 반복하면서 폭발문자열이 나오는지 확인한다

3. 폭발문자열이나올경우 폭발문자열의 길이만큼 stack2를 pop하고
   폭발문자열의 길이만큼 stack2에서 팝한것을 stack1에 푸쉬

2~3을 끝날때까지 반복한다