[골드5] 9935. 문자열 폭발 (C++)

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

9935번: 문자열 폭발

https://heih.tistory.com/51

[골드5] 9935. 문자열 폭발 (Java)

해당 문제 Java 풀이에서 출력함수만 바꿨을 뿐인데 시간초과가 되는걸 확인 후, 혹시 로직이 잘못된 것은 아닌지 검증을 위해 C++로 다시 풀어보았습니다!

---

※  문제를 요약하면 아래와 같습니다.

▶ 기준 문자열과 폭탄 문자열 두가지 입력

▶ 기준 문자열 내에 폭탄 문자열과 같은 문자열은 제거

   ex ) 기준 문자열 : mirkovC4nizCC44

          폭탄 문자열 : C4

         ====> mirkovC4nizCC44 -> mirkovnizC4 -> mirkovniz

▶ 입력은 첫 줄에 기준 문자열, 둘째 줄에 폭탄 문자열 입력

▶ 출력은 폭탄 문자열을 전부 지운 문자열, 문자열이 비어있을 경우 'FRULA' 출력

◈ Input -1

mirkovC4nizCC44
C4

◈ Output -1

mirkovniz

◈ Input -2

12ab112ab2ab
12ab

◈ Output -2

FRULA

---

 ◎  아래와 같이 솔루션을 정리하였습니다.

▶ 기존 문자열에서 문자를 하나씩 스택 자료형에 추가

▶만약 폭탄 문자열의 마지막 문자와 같은 데이터 발견 시, 해당 인덱스 부터 앞으로 다시 탐색

▶앞으로 다시 탐색하는 과정에서 폭탄 문자열과 일치하면 제거 (stack 자료구조를 vector STL로 구현)

▶System.out.println() 출력 하면 계속 시간 초과 발생 => BufferedWriter 사용

▶탐색 인덱스 비교시 (int) 형변환 (vector, string의 size는 unsigned int형으로 반환)

#include <iostream>
#include <vector>
#include <string>

using namespace std;

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

	vector<char> listResult;

	string strTemp, strBomb;

	cin >> strTemp >> strBomb;


	for (int i = 0; i < strTemp.length(); i++) {
		listResult.push_back(strTemp[i]);

		if (listResult.size() >= strBomb.length() &&
			listResult.back() == strBomb[strBomb.length() - 1]) {

			bool bSearch = true;
			int nIndex = strBomb.length() - 1;
			for (int j = listResult.size() - 1; j > (int)(listResult.size() - 1 - strBomb.length()); j--) {
				if (listResult.at(j) != strBomb[nIndex]) {
					bSearch = false;
					break;
				}
				nIndex--;
			}

			if (bSearch) {
				
				for (int j = 0; j < strBomb.length(); j++) {
					listResult.pop_back();
				}
			}

		}
	}


	if (listResult.empty())
		cout << "FRULA" << endl;
	else {
		for (int i = 0; i < listResult.size(); i++) {
			cout << listResult.at(i);
		}
	}

	return 0;
}

---

그냥 진짜로 java가 느린거였네요.. 시간만 날렸다..