C++ [문자열 폭발_백준] / #string 클래스 사용

Problem

---

문자열 폭발_백준

9935번: 문자열 폭발

 

1. 문자열과 폭발 문자열이 주어졌을 때 문자열에서 폭발 문자열과 일치하는 부분 문자열이 존재할 경우 문자열에서 부분 문자열을 제거한다.

2. 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.

3. 새로 생긴 문자열에 폭발 문자열이 포함되지 않을때까지 1번을 반복

 

처음 바로 떠오른 풀이 방식은 재귀함수를 이용하여 문자열에서 폭발 문자열을 체크하고 삭제하는 함수를 만들어서 이를 반복하는 식으로 구현하였다.

 

처음에 메모리초과가 떠서 재귀함수의 지역 변수를 반복 생성한 것이 원인이라고 생각하여 전역변수로 바꾸었으나 이번에는 시간초과가 떴다.

아래는 틀린 나의 풀이 방법

#include <iostream>
#include <string>

using namespace std;
string str, boom;
int start;

void solving()
{
	start = str.find(boom);
	if (str.find(boom) != string::npos)
	{
		str.erase(start, boom.length());
		solving();
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> str >> boom;
	solving();
	if (str.empty())
	{
		cout << "FRULA";
	}
	else
	{
		cout << str;
	}
	return 0;
}

 

Solve

---

결국 그냥 구글링을 통해 풀이법을 찾아서 해결하였다.

풀이법은 다음과 같다.

 

1. 문자열을 하나씩 answer문자열에 넣는다.

2. answer문자열이 폭발문자열의 길이와 같거나 크면 이전의 폭발문자열 길이만큼의 문자열과 폭발문자열을 비교하여 같으면 string 클래스의 멤버함수 erase를 이용하여 문자열 제거

3. 결과로 answer문자열이 empty이면 FRULA 출력 아니면 answer 문자열 출력

#include <iostream>
#include <string>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	string str, boom;
	cin >> str >> boom;

	string ans;

	for (int i = 0; i < str.length(); i++)
	{
		ans += str[i];
		if (ans.length() >= boom.length())
		{
			for (int j = 0; j < boom.length(); j++)
			{
				if (ans[ans.length() - boom.length() + j] != boom[j])
				{
					break;
				}
				if (j == boom.length() -1)
				{
					ans.erase(ans.length() - boom.length(), boom.length());
				}
			}
		}
	}
	if (ans.empty())
	{
		cout << "FRULA";
	}
	else
	{
		cout << ans;
	}
	return 0;
}