9935 문자열 폭발

단순하게 생각해보면 문자열을 비교하는 함수를 사용하여 쉽게 풀 수 있을 것 같지만, 함정이 숨어있다.

입력 문자열 길이가 1,000,000이다. 즉, 비교 함수로 하나씩 비교하면, 시간초과가 난다..

때문에 다른 방법으로 접근해야 한다.

코드를 참고해보니 핵심은 폭발 문자열의 마지막 문자와 입력 문자열의 마지막 문자를 비교하고 일치한다면, 나머지까지 비교하는 것이다.

결과 문자열에 입력 문자열을 하나씩 저장해가면서 다음과 같은 룰을 따른다.

1. 폭발 문자열의 마지막 문자를 입력 문자열과 비교한다.
   • 같다면 폭발 문자열의 나머지 문자와 비교한다.
   • 다르면 결과 문자열에 그대로 저장한다.
2. 1번에서 폭발 문자열의 나머지 문자들과 모두 일치한다면, 폭발 문자열의 길이만큼 결과 문자열의 인덱스에서 뺀다.

다른 사람의 코드도 참고해보니 스택을 사용하는 방법과 char 배열을 사용하는 방법으로 나뉘는데, char 배열을 사용하는게 더 직관적이여서 참고했다.

정답코드

#include <iostream>
#include <string>
using namespace std;
#define MAX_SIZE 1000000
char result[MAX_SIZE];
int main()
{
	string str, bomb;
	cin >> str >> bomb;
	int len = str.size(), idx = 0;
	int bombLen = bomb.size();
	for (int i = 0; i < len; i++) {
		result[idx++] = str[i];
		if (result[idx - 1] == bomb[bombLen - 1]) {
			//예외 : 결과 문자열의 길이가 폭발 문자열의 길이보다 작다면 패스
			if (idx - bombLen < 0)
				continue;
			bool boom = true;
			//폭발 문자열의 나머지 문자들과 비교
			for (int j = 0; j < bombLen; j++) {
				if (result[idx - j - 1] != bomb[bombLen - j - 1]) {
					boom = false;
					break;
				}
			}
			//폭발 문자열과 모두 일치하는 경우
			if (boom) {
				idx -= bombLen;
			}
		}
	}
	if (!idx) {
		printf("FRULA\n");
	}
	else {
		//계산한 인덱스만큼 출력
		for(int i = 0; i<idx; i++)
		printf("%c", result[i]);
	}
	return 0;
}