백준 9935) 문자열 폭발_G5

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

9935번: 문자열 폭발

이 문제는 스택을 활용할 수있으면 충분히 풀 수 있는 문제이다.

#include <iostream>
#include <stack>
#include <algorithm>

int main(void)
{
	std::stack<char> stk;		//문자를 담을 스택
	std::string input;			//입력받은 문자
	std::string boomWord;		//폭발문자열
	int boomcount = 0;			//폭발카운트	폭발문자열 길이만큼 커짐

	std::cin >> input;
	std::cin >> boomWord;

	//입력받은 문자열의 길이만큼 반복
	for (int i = 0; i < input.size(); i++)
	{
		//스택의 크기가 boomWord의 크기이상이고 && 현재입력받을 문자가 폭발문자열의 마지막 문자와 같으면,
		if (stk.size() >= boomWord.size() - 1 && input[i] == boomWord[boomWord.size() - 1])
		{
			std::string tmp;		//스택의 안이 폭발문자열이 아닐경우, 스택에 되돌리기 위한 임시저장소
			boomcount = 1;

			//폭발문자열의 마지막문자는 확인됐으므로 그 다음 문자들을 스택에서 차례대로 체크
			for (int j = 0; j < boomWord.size() - 1; j++)
			{
				if (!stk.empty() && stk.top() == boomWord[boomWord.size() - 2 - j])
				{
					boomcount++; //스택안에서 폭발문자열의 문자가 발견될때마다 하나씩 증가
					tmp += stk.top(); //최종적으로 스택의 안이 폭발문자열이 아닐경우 대비
					stk.pop(); //폭발문자열의 문자임을 확인했으므로 pop
				}
				else break; // 폭발문자열이 아니므로 루프탈출
			}

			//위의 for문을 마지막까지 진행하면 boomcount는 boomWord의 길이와 같아짐.
			if (boomcount == boomWord.size())
			{
				continue;
			}
			//boomcount가 boomWord의 길이가 아닌경우,
			else
			{
				//스택에서 pop시킨 문자들을 다시 스택에 돌려놓음
				for (int u = tmp.size() - 1; u >= 0; u--)
				{
					stk.push(tmp[u]);
				}
			}
		}

		stk.push(input[i]);
	}

	//문자열이 다 폭발하여 남은게 없음
	if (stk.empty())
		std::cout << "FRULA" << std::endl;
	else
	{
		std::string result;
		//스택에 들어가있는 문자들을 원래순서대로 해줌
		while (!stk.empty())
		{
			//result.insert(0, 1, stk.top());
			result.push_back(stk.top());
			stk.pop();
		}
		reverse(result.begin(), result.end());
		std::cout << result << std::endl;
	}

	return 0;
}

 

처음풀었을때는 시간초과가 발생했다.

시간초과가 발생한 부분은.

스택으로 문자들이 역순으로 저장되어있기 떄문에 마지막에 스택에 담아있는 문자들을 string형 result변수를 담을 떄,

result.insert(추가할 위치, 추가할 문자 갯수, 추가할 문자)함수를 사용하여 문자열을 다시 역순으로 추가하는 부분이다.

여러가지 부분을 수정해보며 이 부분에서 계산시간이 많이 걸리는 것을 알고 위의 코드와 같이,

insert()함수를 사용하지 않고 역순인 상태 그대로 string에 문자를 하나씩담아주고 마지막에 reverse()함수를 사용하여 

원래 순서대로 돌려주었다.

insert()함수가 이렇게 계산시간이 많이 걸리는 함수인가?

다시 알아봐서 추가하도록 하자.

추가적으로 string형 변수에 대하여 += 연산자는 좋지 못하다.

문자열을 새로 생성하여 복사하는 느낌이라고 한다.

대신 pushback()함수를 사용하여 계산시간을 줄일 수 있다.