문제 링크

---

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

문제 풀이

---

문자열과, 폭발 문자열이 입력으로 주어질 때 문자열에서 폭발 문자열을 찾아 제거하는데 폭발 문자열을 제거하여 재구성된 문자열안에 폭발 문자열이 또 있다면 폭발 문자열이 없을때까지 반복해서 제거해주면 되는 문제로 다음과 같은 접근방식으로 문제를 풀었다.

• 문자열을 순차적으로 탐색하면서 스택에 저장
• 스택의 top 과 폭발 문자열의 마지막 문자가 동일한지 비교
• 동일하다면 스택의 크기가 폭발 문자열의 크기보다 크거나 같은지 확인 ( 범위를 벗어나는것을 방지 )
• 스택의 이전값들과 폭발 문자열을 비교
• 스택의 이전값들이 폭발 문자열과 동일하다면 폭발 문자열의 길이만큼 스택에서 제거

단, 스택은 반복자가 존재하지 않아 이전값들을 비교하는데 어려움이 있을거라고 생각해서 벡터를 스택처럼 구현하여 문제를 풀었다.

TMI) 처음 문제를 풀 때 find 함수를 이용해서 풀면 되는 쉬운 문제라고 생각했으나, find 함수를 이용 할 경우 시간초과가 발생했다. 해당 코드도 같이 첨부.

정답 코드

---

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>


using namespace std;

int main() {
	string str1; //입력 문자열
	string boomb; //폭발 문자열
	cin >> str1 >> boomb;

	vector<char> answer;

	

	//#2
	for (int i = 0; i < str1.size(); i++) {
		int count = 0;
		answer.push_back(str1[i]);
		if (answer.back() == boomb[boomb.size() - 1]) { //벡터의 마지막 값과 폭탄 문자열의 마지막 값을 비교
			if (answer.size()>=boomb.size()) { //예외처리
				int count = 0; // 벡터의 이전 값들과 폭탄 문자열의 값들을 비교하며 같은 값을 카운트
				for (int j = 0; j < boomb.size(); j++) { //벡터의 크기만큼 비교
					if(answer[answer.size() - boomb.size() + j] == boomb[j]) count++; 
				}
				if (count==boomb.size()) { 
					answer.erase(answer.end() - boomb.size(),answer.end());
				}
			}
		}
	}
	if (answer.size() == 0) {
		cout << "FRULA";
	}
	else {
		for (int i = 0; i < answer.size(); i++) {
			cout << answer[i];
		}
	}

	/* #1 시간초과
	while(str1.find(boomb)!=string::npos) {
		int n = str1.find(boomb);
		string from = str1.substr(0, n);
		string to = str1.substr(n + boomb.size());
		str1 = from + to;
	}
	if (str1.size() == 0) {
		cout << "FRULA";
	}
	else {
		cout << str1;
	}
	*/



	return 0;
}