[백준] 9935번 문자열 폭발 C++

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

9935번: 문자열 폭발

 

코드 풀이 

재밌는 문자열 처리 문제였습니다. 처음에는 스택을 쉽게 생각했는데 스택에서 빼고 폭발문자열(target) 과 확인하는 과정에서 어떻게 확인하고 다시 넣을지 고민했었습니다. 

그래서

1.단순히 stack 을 이용하여 하나씩 넣다가 폭발문자열의 마지막 문자를 만났을때 다시 stack에서 폭발문자열 크기만큼 빼내서 확인후 다시 넣는 풀이방법

 

2. vector와 idx 변수를 사용하여 stack 처럼 푸는 방법 두가지 방법으로 풀어보았습니다.

 

1의 방법의 경우 stack에서 다시 빼고 target문자와 확인할때 reverse함수를 사용해야합니다.

 

소스 코드 (stack이용)

#include<iostream>
#include<queue>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;

int main(){
	stack<char> st;
	string a, target;

	cin >> a >> target;
	string check = "";
	for (int i = 0; i < a.size(); i++) {
		st.push(a[i]);
		if (st.size() >= target.size() && st.top() == target[target.size() - 1]) { //폭탄문자열이 들어갈수 있고 마지막 문자가 폭탄문자열과 같을때
			check = "";
			for (int j = 0; j < target.size(); j++) { //꺼내서ㄱ확인
				
				check += st.top();
				st.pop();

			}
			reverse(check.begin(), check.end());
			if(check != target) {//다르면 다시 넣어야함
				for (int k = 0; k < check.size(); k++) {
					st.push(check[k]); //다시넣기
				}
			}

		}


	}
	string result;
	if (st.empty()) cout << "FRULA";
	while(!st.empty()){
		result += st.top();
		st.pop();

	}
	reverse(result.begin(), result.end());
	cout << result;


	return 0;
}

 

소스 코드 (vector + index 변수 사용)

#include<iostream>
#include<queue>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
char result[1000000];
int main(){
	string a, target;
	cin >> a >> target;
	int idx = 0;
	bool flag = false;
	for (int i = 0; i < a.size(); i++){
		result[idx] = a[i];
		flag = false;
		if (result[idx] == target[target.size() - 1]) {

			for (int j = 0; j < target.size(); j++) {
				if (result[idx - j] != target[target.size() - 1 - j]) {
					flag = true;
					break;
				}
			}
			if (flag == false) {
				idx -= target.size(); // 덮어쓰기위해 다시 앞으로 인덱스이동(전부사라지면 idx=-1)
			}
		}
		idx++;



	}
	if (idx == 0) cout << "FRULA";
	else {
		for (int i = 0; i < idx; i++) {
			cout << result[i];
		}
	}
	return 0;
}