[PS] 백준 9935번 문자열 폭발

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

문제 설명

최장 길이 1,000,000의 입력 문자열과 최장 길이 36의 폭발 문자열이 주어진다. 입력 문자열에는 폭발 문자열이 들어있을 수 있고, 폭발 문자열이 존재하는 경우, 입력 문자열에서 폭발 문자열은 제거된다. 제거된 후의 문자열에서도 폭발 문자열이 존재하지 않을 때 까지 위 과정을 반복하고 최종 문자열을 출력한다. 최종 문자열이 ""인 경우, "FRULA"를 출력한다. 그리고 중요한 조건이 주어지는데, 바로 "폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다" 조건이다.

1. 가장 먼저 떠올리는 방법은 폭발 문자열이 존재하지 않을 때까지 입력 문자열을 반복해서 스캔하는 방법이다. 떨어져 있던 문자들이 폭발로 인해 이어지게 되어 폭발 문자열이 되는 경우를 다음 반복에서 처리하면 되기때문에 비교적 간단하다. 하지만 이 방법은 폭발 문자열이 "AB"라고 할 때, "AAA...ABBB.....B" 와 같이 A 가 50만, B 가 50만 개 있는 문자열의 정답을 구해보면, 복잡도가 O(n^2)이 될 것이라는 것을 알 수 있다. 시간 초과이다.

2. 입력 문자열에서 폭발 문자열을 찾고 폭발 뒤에 이어지는 문자열에 대해서 폭발 문자열인지 아닌지 비교하고를 반복하는 방법을 쓸 수 밖에 없다는 것을 알게 되었다. 구현 방법에는 여럿있겠으나 Deque을 이용하기로 한다. Stack 의 push(), pop() 연산이 필요하고, 임의 접근이 있으면 편리하기 때문이다.

   입력 문자열의 뒤에서 부터 시작한다. 해당 문자를 stack에 push() 하고 스택 크기가 폭발 문자열 길이보다 클 때만 폭발 문자열의 길이만큼 stack의 내용을 꺼내서 같은 문자열인지 비교한다. 같으면 폭발 문자열의 길이만큼 stack에서 pop() 해주고 다음 반복을 진행하면 끝이다. stack에 들어있는 문자들은 폭발 문자열인지 판단되기를 기다리는 문자들이다. 폭발 후 폭발 문자열의 좌측과 우측에 있던 문자열이 이어지면서 폭발 문자열이 되는 경우를 고려해야하기 때문에 stack 의 내용을 계속 비교해야 한다.

중요한 조건인 "폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다" 조건은 폭발 문자열이 같은 문자를 두 개 이상 포함하게 되면 2개 이상의 폭발 문자열이 Overlap 될 수 있기 때문에 폭파 순서에따라 결과가 달라지게 된다. 본 문제에서는 같은 문자를 두 개 이상 포함하지 않으므로 어떻게 폭파시키든 결과는 하나만 나온다.

Java로 푸는 경우 메모리가 빠듯하다. 아래코드에서 comp() 함수를 StringBuilder로 String을 만든 후 equals()로 비교하니 메모리 초과가 발생했었다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;

class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static Scanner sc = new Scanner(System.in);

	static StringTokenizer st;

	char[] input;
	String explosive;
	Deque<Character> stack;

	public static void main(String[] args) throws IOException {
		Main ps = new Main();

		ps.solution();
	}

	void printResult() throws IOException {
		if (stack.isEmpty()) {
			System.out.println("FRULA");
			return;
		}
		
		while (!stack.isEmpty()) {
			bw.append(stack.pop());
		}

		bw.flush();
	}

	void explode() {
		for (int i = 0; i < explosive.length(); i++) {
			stack.pop();
		}
	}

	boolean comp() {
		Iterator<Character> iter = stack.iterator();
		for (int i = 0; i < explosive.length(); i++) {
			if (iter.next() != explosive.charAt(i)) {
				return false;
			}
		}

		return true;
	}

	void solution() throws IOException {
		input = br.readLine().toCharArray();
		explosive = br.readLine();
		stack = new ArrayDeque<>();

		/**
		 * i := input 배열의 index
		 */
		for (int i = input.length - 1; i >= 0; i--) {
			stack.push(input[i]);
			if (stack.size() < explosive.length()) {
				continue;
			}

			// explosive 배열과 길이가 같거나 커졌으므로 같은 문자열인지 비교할 수 있다
			if (comp()) { // 비교해서 같으면
				explode();
			}
		}

		printResult();
	}
}