[백준OJ] 9935번 문자열 폭발

 

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

9935번: 문자열 폭발

---

풀이

1. 먼저 입력받은 문자를 ret에 추가시킨다.

2. 해당 문자와 폭발하는 문자열의 맨 뒷자리가 같은지 확인해본다.

2-1. 만약 같으면, ret문자열의 맨뒤부터해서, 폭발하는 문자열이 모두 포함된지 확인한다.

2-1-1. 만약 폭발하는 문자열이 모두 포함된 상태라면, ret을 폭발하는 문자열의 개수만큼 pop_back()해준다.

3. 다음 문자를 반복해서 실행해준다.

 

시간복잡도

문자열을 한번 탐색하면 끝이므로 (폭발하는 문자열이 포함된지 검사와 pop_back()하는것은 폭발하는 문자열의 최대길이가 최대 36이므로 O(1)이라고 해도된다.) O(N)이 된다.

 

코드

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

string input, boom;

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

	string ret = "";
	int bind = boom.size()-1;
	for (int i = 0; i < input.size(); i++) {
		//1.일단 추가
		ret += input[i];

		int rind = ret.size() - 1;

		//2.현재 입력된값과 boom의 맨 뒤가 같은지 비교, (boom의 사이즈보다 ret의 사이즈가 작으면 무시)
		if (ret[rind] == boom[bind]&&rind>=bind) {
			//2.1 뒤부터 boom의 문자열과 같은지 확인
			bool flag = true;
			for (int j = 0; j <= bind;j++) {
				if (ret[rind-j] != boom[bind-j]) {
					flag = false;
					break;
				}
			}
			//2.1.1 만약 현재 입력받은 문자열까지가 boom이면
			if (flag){
				//boom의 개수만큼 pop_back();
				int t = bind+1;
				while (t--) {
					ret.pop_back();
				}
			}
		}
	}
	if (ret == "") {
		cout << "FRULA\n";
	}
	else {
		cout << ret;
	}
	
	return 0;
}