백준 9935 문자열 폭발

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

9935번: 문자열 폭발

 

Stack을 활용하는 문제다. 정확히 말하면 STL이나 여타 라이브러리가 아니라 Stack의 LIFO을 이용한다. 

백만이나 되는 Input과 2초 밖에 안되는 시간제한을 고려했을 때 별다른 선택지가 없었다.

 

비교 연산을 1억번 할 때 1초 정도가 들기 때문에 2초면 비교 연산만 고려해도 2억번 이내로 해결해야한다.

하지만 Input이 100만 이기 때문에 N^2는 최악의 경우 100 0000 * 100 0000 = 1 0000 0000 0000 가 된다.

 

/* 문자열 폭발 */

#include <iostream>
#include <string>
#include <cstring>

using namespace std;

string s, t;
char res[1000000 + 1];

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> s >> t; 

	int s_length = s.length();
	int t_length = t.length();
	int idx = 0;
	bool flag;

	for (int i = 0; i <= s_length; i++) { // O(N) 의 시간 복잡도로 해결해야 하는 문제다.
		res[idx++] = s[i];

		if (res[idx - 1] == t[t_length - 1]) { // 방금 입력한 문자가 bomb 문자의 제일 마지막과 같다면
			// 역순으로 추적해나간다.
			flag = true;

			for (int trace = 0; trace < t_length - 1; trace++) {
				if (res[idx - t_length + trace] != t[trace]) { // 같지 않다면 bomb가 안됨
					flag = false;
					break;
				}
			}

			if (flag == true) { // Bomb!
				idx -= t_length;
			}
		}
	}

	if (strlen(res) == 0) {
		cout << "FRULA";
	}
	else {
		cout << res;
	}

	return 0;
}