[알고리즘] 문자열 폭발 (백준 9935번)

9935번: 문자열 폭발

 폭발 문자열, 즉 특정 패턴을 찾아서 매칭되면 그 패턴에 해당하는 문자열을 삭제하고, 새로 만들어진 문자열에서 또 패턴을 찾아 삭제하라는 문제이다.

 

 당연하겠지만 String.replaceAll로 반복문을 돌리는 것은 메모리 초과, 혹은 시간 초과로 불가능하다. O(N) 만큼의 시간복잡도로 패턴을 찾아 파괴하는 것이 포인트이다.

 

1. failureFunction 만들기

KMP를 응용하여 failureFunction을 만들어서 비교 문자가 같지 않은 경우 pattern 인덱스가 돌아갈 곳을 지정해둔다.

 

 

2. index_stack 만들기

어떻게 보면 이게 핵심인데 폭발 문자열을 발견하고 문자열을 폭파시킨 후, pattern 인덱스가 돌아갈 곳을 지정하는 것이다.

 

 만약 'patternCC44pattern' 문자열에서 'C4' 패턴을 찾아 폭파시킨다고 가정하자. 그럼 첫 번째로 8~9번 index의 문자열 C4를 폭파시킬 것이다. 이후 생성되는 문자열은 'patternC4pattern' 로 폭파시킨 자리에 다시 C4 패턴이 생성되므로 다시 폭파를 시켜야한다.

 이 때 만약 pattern 인덱스가 다시 0번부터 시작하게 되면 폭파 직후 비교를 시작하는 text의 8번 index '4'는 현재 비교 문자('C') 와 같지 않은 것으로 판단하고 넘어가버리게 될 것이다. 이 때를 대비하여 폭파 직후에 pattern 인덱스가 7번 index 'C'와 비교를 마친 바로 직후인 것처럼 다시 작동할 수 있도록 index_stack에 돌아갈 곳을 지정하는 것이다. (말이 너무 어렵다...)

 

 말로 설명하면 어려우니 도식화해서 표현하겠다.

첫 번째 폭파지점까지 도달했을 때 상황

폭파직후 상황, 폭파한 pattern 길이만큼 pop 후 top에 있는 index를 꺼내와서 패턴 인덱스로 지정해준다.

 만약 첫 번째 폭파 직후 그 전에 문자가 'C'가 아닌 다른 문자였다면 아마 index_stack에는 0이 들어있었을 거고 pattern은 다시 index 0부터 비교를 시작했을 것이다.

 

 

3. char_stack 사용

 문자열을 폭파, 즉 삭제할 때 String의 replace나 Stringbuilder의 delete 등의 내장 함수를 사용하면 기본적으로 문자열 처음부터 탐색을 다시 시작하기 때문에 O(N^2)의 시간 복잡도로 늘어나버린다.

 때문에 정확하게 pattern 문자 길이만큼의 시간만 투자하여 삭제를 하기 위해 stack을 만들어서 결과 문자열을 만들어 나간다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {

	static void failureFunction(int p[], StringBuilder pattern)
	{
		int j = 0;

		for(int i = 1;i < pattern.length();i++)
		{
			while(j > 0 && pattern.charAt(i) != pattern.charAt(j))
				j = p[j-1];

			if(pattern.charAt(i) == pattern.charAt(j))
				++j;
		}
	}

	public static void main(String[] args) {

		try
		{
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

			StringBuilder text = new StringBuilder(br.readLine());
			StringBuilder pattern = new StringBuilder(br.readLine());

			//pattern 인덱스가 돌아갈 곳 지정
			Stack<Integer> index_stack = new Stack<>();

			//결과 문자열 저장
			Stack<Character> char_stack = new Stack<>();

			int p[] = new int[pattern.length()];

			failureFunction(p, pattern);

			int j = 0;

			//text 길이만큼 순회
			for(int i = 0;i < text.length();i++)
			{
				while(j > 0 && text.charAt(i) != pattern.charAt(j))
					j = p[j-1];

				//문자 push
				char_stack.push(text.charAt(i));

				//문자가 같은 경우
				if(text.charAt(i) == pattern.charAt(j))
				{
					//패턴 매칭 완료
					if(j == pattern.length() - 1)
					{
						//패턴 길이만큼 pop 함으로써 문자 삭제
						char_stack.pop();
						for(int k = 0;k < pattern.length()-1;k++)
						{
							index_stack.pop();
							char_stack.pop();
						}

						//pattern 인덱스 j가 돌아갈 곳을 지정
						if(!index_stack.isEmpty())
							j = index_stack.peek();
						else
							j = 0;
					}
					//일부 일치
					else
						index_stack.push(++j);

				}
				//문자가 같지 않다면 현재 pattern index push
				else
					index_stack.push(j);
			}

			if(!char_stack.isEmpty())
			{
				for(char a: char_stack)
					bw.write(a);
			}
			else
				bw.write("FRULA");

			bw.close();
		}
		catch (Exception e)
		{
			e.printStackTrace();
		}

	}
}