[9935] 문자열 폭발 - 문자열/Stack ★★★☆ / 복습 ○

[ 문제 ] : https://www.acmicpc.net/problem/9935

9935번: 문자열 폭발

---

[ 문제 접근 ]

 

호기롭게 문자열 문제라고 생각하고 구현해서 풀으려고 했다.

 

구현에 걸린 시간도 시간이지만 너무 난잡한 코드가 나왔다..

 

아니나 다를까 채점하면 시간초과..

 

그래도 예제 몇개 입력해보면 정답 나오는거에 만족하고

 

다른 풀이를 찾으려고 했는데 어떻게 무슨 방법을 사용해야할지 감이 안잡혔다.

 

포기하고 구글링하면서 다른 사람 코드를 쑥 훑었다. ( 자세히 보면은 안된다.)

 

코드에 stack이 보였고 전체적으로 길이가 그렇게 길지가 않았다.

 

스택으로 한번 풀어보기로 했다.

 

---

[ 첫번째 코드 ] × ( 시간초과 )

 

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

// substr(pos,count) ->  pos가 str 인덱스 범위 밖일때 런타임 오류 발생해야하는데 VS는 발생 안시킨다.

using std::cout; using std::cin;
using std::vector; using std::string;

string str, bomb;


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

	cin >> str >> bomb;

	size_t prev = 0;
	size_t current = str.find(bomb, prev);

	string answer = "";
	bool is_in = false;
	bool flag = false;

	while (current != string::npos ) {
		is_in = true;
		string substring = str.substr(prev,current-prev); //mirkov
		if(!flag) answer += substring;
		else {
			answer = substring;
			flag = false;
		}

		if (current + bomb.length() >= str.length()) {
			prev = 0;
			str = answer;
			current = str.find(bomb, prev);
			flag = true;
		}
		else {
			prev = current + bomb.length();
			current = str.find(bomb, prev);

			if (current == string::npos) {
				answer += str.substr(prev, current - prev);
				prev = 0;
				str = answer;
				current = str.find(bomb, prev);
				flag = true;
			}
		}
	}
	
	if (answer.length() == 0 && is_in) answer = "FRULA";
	if (!is_in) answer = str;
	cout << answer;



	return 0;
}

 

[ 두번째 코드 ]

 

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<stack>
#include<deque>


// substr(pos,count) ->  pos가 str 인덱스 범위 밖일때 런타임 오류 발생해야하는데 VS는 발생 안시킨다.

using std::cout; using std::cin;
using std::vector; using std::string;

string str, bomb;
std::stack<char> st;


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

	cin >> str >> bomb;
	
	int cnt = 0;
	for (int i = 0,j=0; i < str.length();i++) {
		st.push(str[i]);
		if (str[i] == bomb.back() && st.size() >= bomb.size()) {
			string temp ="";
			for (int i = 0; i < bomb.size(); i++) {
				temp += st.top();
				st.pop();
			}

			std::reverse(temp.begin(), temp.end());

			if (bomb != temp) {
				for (auto& elem : temp) {
					st.push(elem);
				}
			}
		}

	}
	if (st.empty()) {
		cout << "FRULA";
		return 0;
	}
	std::deque<char> answer;  // 남은 스택 값을 출력하려고 덱 만들었는데 reverse로 해도 된다.
	while (!st.empty()) {  
		answer.push_front(st.top());
		st.pop();
	}

	for (auto& elem : answer) {
		cout << elem;
	}
	return 0;
}

 

 

---

[ Key Point ]

 

👉 쉽지 않았던 문제.  그냥 많이 푸는게 정답인것 같다.

 

---

[ 다른 사람 풀이 ]

 

ref :: https://torbjorn.tistory.com/379