[BOJ] 9935 : EKSPLOZIJA

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

---

문자열 문자열처리

 처음에는 KMP알고리즘을 사용해서 A  문자열에서 B 문자열을 다 찾고, 그 후 B 문자열을 다 지워주고, 다시 갱신된 문자열 A에 대해서 KMP 알고리즘을 사용해서 B 문자열을 다 찾는 방식으로 진행했습니다. 하지만, 시간초과 문제에 직면했고, 스택으로 문제를 해결할 수 있다는 힌트를 얻어서 순회하는 방식으로 문제를 다시 접근했습니다. ( 스택을 쓰지는 않았습니다! )

● A 문자열을 앞에서부터 순회하며 새로운 정답 문자열 C에 A를 넣어주며, C의 끝에서 B 문자열을 마주하게 되면 B 문자열을 지워주는 방식으로 진행하면 O(A.length()) 만에 문제를 해결할 수 있습니다.

ex ) 

mirkovC4nizCC44

C4

정답 문자열 C에 mirkovC 순서로 차례대로 push한 후, 4가 추가되면 C 문자열의 끝에 C4가 존재하므로 C4를 erase해줍니다. 그러면 이제 정답 문자열은 mirkov가 됩니다. 그 후 nizC를 push 해주고 mirkovnizC 상태에서 C4 가 들어와서 erase가 진행됩니다. 그 후 4가 들어와 또 C4가 존재하므로 erase해줍니다.

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

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	string A, B, result;
	cin >> A >> B;
	int n = A.size(), m = B.size();
	for (int i = 0; i < n; i++) {
		result.push_back(A[i]);
		// result의 끝과 B의 끝이 같고, result에서 B를 뺄 수도 있는 크기
		if (result.size() >= B.size() && result.back() == B.back()) {
			// result의 끝에 B가 걸려있는지 확인해보자.
			bool flag = true;
			for(int j= 0; j < m; j++)
				if (result[result.size() - m + j] != B[j]) {
					flag = false;
					break;
				}
			if (flag) // 폭탄제거해야됨
				result.erase(result.size() - m, m);
		}
	}
	if (result.size() == 0) cout << "FRULA";
	else cout << result;
	return 0;
}

---