백준9935 - 문자열 폭발

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

9935번: 문자열 폭발

문자열을 이용하여 푼 문제다. 시간 초과가 많이 났는데 이유는 string의 함수들의 시간 복잡도를 계산하지 못한 것이 이유였다. 처음에는 문자열의 원하는 부분을 substr로 잘라내어 패턴과 같은 곳을 erase로 지우려 하였는데 두 함수 모두 시간 복잡도가 O(n)으로 포문에 들어갈 경우 많은 시간을 잡아 먹는다는 것을 알게 되었다. 그래서 전략을 수정하여 패턴을 찾으면 패턴이 처음에 시작하는 부분부터 다음에 올 글자를 넣는 작업을 수행하였다. 그러면 현재 문자열을 지우지 않고도 새로운 문자열을 넣을 수 있게 된다.

 

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

char ans[1000001]; //정답을 담을 공간

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int idx = 0; //어디에 위치할 글자인지 나타내주는 index변수
	string s1, s2; //s1은 입력한 문자열, s2는 패턴
	

	cin >> s1 >> s2;
    
    	//주어진 문자열을 답으로 바꾸는 과정, 글자들을 조합하여 패턴을 찾는다.
	for (int i = 0; i < s1.size(); i++) {
		bool check = false;
		ans[idx++] = char(s1[i]); //현재 글자를 답을 넣을 공간을 가리키는 idx위치에 삽입
        
        	//패턴의 끝자리와 현재의 입력한 글자가 같고 현재까지 넣은 문자의 갯수가 패턴의 길이보다 크면
		if (s1[i] == s2[s2.size() - 1] && idx >= s2.size()) { 
			int cnt = s2.size() - 2; //패턴의 뒤에서 두번째 위치부터 시작
			for (int j = idx - 2; j >= 0; j--) { //현재까지 입력한 위치인 뒤에서부터 두번째 시작
				if (cnt < 0) { //패턴을 다 찾은 경우
					break; //탈출
				}
				if (ans[j] != s2[cnt]) { //패턴이 어긋난 경우
					check = right; //참으로 바꾸고
					break; //탈출
				}
				cnt--; //패턴의 인덱스를 앞으로 이동
			}
			if (!check) { //패턴을 온전히 찾은 경우
				idx = idx - s2.size(); //패턴의 길이만큼 앞으로 이동한다.
				if (idx < 0) { //패턴의 길이만큼 이동했는데 음수인 경우
					idx = 0; //맨 처음위치인 0번지 부터 시작
				}
			}
		}
	} 

	if (idx == 0) { //아무런 글자도 입력되지 않은 경우(글자의 조합이 모두 폭탄인 경우)
		cout << "FRULA";
	}
	else { //글자 조합을 하였을 때 모두 폭탄이 아니고 남는 글자가 있을 경우
		for (int i = 0; i < idx; i++) { //출력
			cout << ans[i];
		}
	}
}