[백준][9935번] 문자열 폭팔

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

9935번: 문자열 폭발

 

풀이과정 (c++)

1. 처음 string의 find를 이용해 풀었으나 시간초과가 발생하여 스택구조를 이용하였다.

 

2. 문자열을 입력받고 스택배열에 넣으면서 폭발단어의 마지막과 일치하게 되면, 폭발단어와 일치하는지를 비교하였다.

 

3. 일치 할 경우 스택배열의 인덱스를 붐 사이즈 만큼 줄여주면 덮어씌어지게 된다.

 

4. 마지막 출력의 경우에도 st의 배열의 idx만큼 출력해야 한다. (지우면서 남아 있는 것이 존재 할 수 있음)

 

 

소스코드

#include <stdio.h>
#include <string>
#include <iostream>
using namespace std;
string boom;
string word;
char st[1000000];
int main()
{
	cin >> word;
	cin >> boom;
	char boomLast = boom[boom.length() - 1];
	char boomSize = boom.length();
	int idx = 0;
	for (int i = 0; i < word.length(); i++) {
		st[idx++] = word[i];
		if (word[i] == boomLast) {
			if (idx - boomSize < 0) {
				continue;
			}
			int boomFind = 1;
			for (int j = 0; j < boomSize; j++) {
				if (st[idx - 1 - j] != boom[boomSize - 1 - j]) {
					boomFind = 0;
					break;
				}
			}
			if (boomFind) {
				idx = idx - boom.length();
			}
		}
	}
	
	if (idx <= 0) {
		printf("FRULA\n");
	}
	else {
		for (int i = 0; i < idx; i++) {
			printf("%c", st[i]);
		}
		printf("\n");
	}
	return 0;
}