백준 9935 폭발문자열

폭발 문자열 (백준 9935)

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

지난번에 푼 ‘에디터’ 문제처럼 deque를 응용하려 풀려하였으나
오히려 코드를 굉장히 복잡하게 작성하였고,
결과적으로 다른 분의 블로그를 참고하여
deque 대신 문자열의 erase 기능을 사용하여 해답을 이해하였다

개인적으로 사용한 방식은
que 2개를 사용하여
문자열을 끝까지 돌며 검사하고,
이후 que를 switching 하여 다시 처음부터 검사하는 방식이였는데
이는 문자열을 반드시 처음부터 끝까지 도는 방식이었기에
이후 시간을 줄이기 힘들었다고 판단하였다

erase 함수가 시간 복잡도가 O(n)이기에
사용하지 않는 것을 전제하고 deque로 풀었으나
사실 erase의 경우, ‘당기는 작업’이 없다고 가정한다면
O(n)이 아니기에 해당 함수를 이용하여 문제를 풀 수 있었던 것 같다

참고 : https://hagisilecoding.tistory.com/127

Code

#include<iostream>
#include<string.h>
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	string a; // 전체 문자열 변수
	string b; // 폭발 문자열 변수
	string t = ""; // 임시 문자열 

	cin >> a >> b;
	const size_t a_len = a.length(); // 전체 문자열 길이
	const size_t b_len = b.length(); // 폭발 문자열 길이

	for (int i = 0; i < a_len; i++)
	{
		t += a[i]; // 문자 추가

		// 임시 문자 길이가 폭발 문자열 보다 크거나 같을 때
		if (t.length() >= b_len)
		{
			// 폭발 문자열 있는지 확인하는 flag
			bool flag = true;

			for (int j = 0; j < b_len; j++)
			{
				// 현재 끝범위 - b_len에서
				// 폭발 문자열인지를 검사한다
				if (t[t.length() - b_len + j] != b[j])
				{
					flag = false;
					break;
				}
			}

			// 폭발 문자열일 경우 삭제 
			if (flag == true)
			{
				t.erase(t.end() - b_len, t.end());
			}
		}
	}

	// 남아 있는 문자열이 없는 경우
	if (t.empty() == true)
	{
		cout << "FRULA";
	}
	else
	{
		cout << t;
	}

	return 0;
}

해결 아이디어

1. 임시 문자열에 입력 문자열을 하나씩 더한다
   이 때, 임시 문자열의 길이가 폭탄 문자열의 길이보다 작다면 진행하지 않음
   
2. 임시 문자열의 (끝자리 - 폭탄 문자열) 과 폭탄 문자열의 처음을 비교한다
   이후 존재하는 경우는 끝자리에 위치하는 폭탄 문자열을 erase 한다
   
3. 반복문 이후, 남아있는 문자열이 없는 경우는 FRULA 호출
   아니면 임시 문자열을 출력한다