[백준 9935번 C/C++] 문자열 폭발

 

[백준 9935번 C/C++] 문자열 폭발

 

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

9935번: 문자열 폭발

 

---

 

해결전략

 

문자열

 

 

---

 

처음 시도한 코드 - 메모리 초과

 

#include <iostream>
#include <vector>
using namespace std;

string input, boom;

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

	cin >> input >> boom;
	
	while(true)
	{
		vector<int> boomLoc;
		bool bBoom = false;
		bool init = false;
		int k = 0;
		for(int i = 0; i < input.size(); i++)
		{
			if (input[i] == boom[0]) {
				init = true;
				k = 0;
				continue;
			}

			if (init)
			{
				k++;

				if (input[i] == boom[k])
				{
					if (k == boom.size()-1) {
						for (int j = boom.size() - 1; j >= 0; j--) {
							boomLoc.push_back(i - j);
						}
						bBoom = true;
						k = 0;
					}
				}
				else {
					init = false;
					k = 0;
				}
			}
		}

		if (bBoom == false) break;

		if(boomLoc.size() > 0)
		{
			string temp;

			int previous = 0;
			for (int i = 0; i < boomLoc.size(); i++)
			{
				temp += input.substr(previous, boomLoc[i] - previous);
				previous = boomLoc[i] + 1;
			}
			temp += input.substr(previous);
			input = temp;
		}
	}

	if (input.size() == 0) cout << "FRULA";
	else cout << input;

	return 0;
}

 

 

---

 

정답 코드

 

#include <iostream>
#include <vector>
#include <string>
using namespace std;

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

	string input, boom;
	cin >> input >> boom;

	vector<char> v; // 문자를 저장

	for(int i = 0; i < input.size(); i++)
	{
		v.push_back(input[i]);

		if(v.size() >= boom.size())
		{
			bool found = true; // 제거할 문자열 발견 여부

			for(int j = 0; j < boom.size(); j++) // v의 마지막 부분이 제거할 문자열과 일치하는지 확인
			{
				if(v[v.size() - boom.size() + j] != boom[j])
				{
					found = false; // 일치하지 않으면 found를 false로 설정하고 반복문 종료
					break;
				}
			}

			if(found) // 제거할 문자열이 발견되면 스택에서 해당 부분 제거
				for(int j = 0; j < boom.size(); j++)
					v.pop_back();
		}
	}

	if(v.empty())
		cout << "FRULA";
	else{
		for(int i = 0; i < v.size(); i++)
			cout << v[i];
    }

	return 0;
}

 

 

 

 

---