백준 9935 문자열 폭발

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다.

 

이 문제는 입력받는 문자열이 100만입니다. 시간 제한이 2초 이므로 폭발 문자열을 찾아가며 없애고 다시 문자열을 돌며 폭발 문자열을 찾는 방식으로 풀게 된다면 시간초과가 나올 것입니다. 따라서 저는 벡터 컨테이너에 문자를 하나씩 넣으며 폭발 문자열의 가장 마지막 문자가 나왔을 때 앞에 있는 원소들과 폭발 문자열의 일치 여부를 비교하여 일치하면 그부분을 pop시키고 다시 남은 문자열들을 넣어가며 폭발 문자열을 모두 제거하였습니다.

 

다음은 코드입니다.

 

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

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	vector<char> s;
	string str1; //입력 문자열 
	string str2; //폭발 문자열 
	bool flag; 
	int num = 0;
	
	cin >> str1 >> str2;
	
	int len = str1.length();
	int len2 = str2.length();
	
	for(int i = 0;  i < len; i++) {
		flag = true;
		int n = i-num; //pop된 횟수만큼 vector의 인덱스 감소 
		s.push_back(str1[i]);
		
		
		for(int j = len2-1; j >= 0; j--) { // 폭발 문자열의 끝과 벡터의 끝부터 차례대로 원소 비교 
			if(s[n--] == str2[j])
				continue;
			else {
				flag = false;
				break;
			}
			}
		if(flag)  //폭발 문자열이 들어있다면 pop시킴 
			for(int k = 0; k < len2; k++) {
				s.pop_back();
				num++; //pop된 횟수 
			}
	}
	if(s.empty())
		cout<<"FRULA";	
	else
		for(auto n: s)
			cout<<n;
	return 0;
	
}