[백준]Baekjoon9935(스택)

문제링크 : https://www.acmicpc.net/problem/9935

풀이

스택을 이용하여 푼 문제이다.

스택에는 pair형식을 통해 첫번쨰 인자로 해당 문자, 두번째 인자로 index를 주었다.

index같은 경우는 폭탄의 각 문자의 index로써 

index를 0으로 초기화 한후 만약 문자열[i] = 폭탄[index]라면 

스택에 문자열[i]와 index를 넣어준 후 index+1을 하여 계속 비교해나가는 식으로 진행하였다.

이 떄 만약 폭탄에 없는 문자가 나왔을 떄는 index로 -1을 넣어 주었으며

이렇게 진행하다가 index가 폭탄의 마지막 index까지 도달하면 

해당 폭탄의 문자열만큼 스택에서 제거해주는 방식을 취하였다.

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

using namespace std;

int main()
{
	string s;
	string bomb;
	cin >> s >> bomb;
	stack<pair<char, int>> stk;
	int index = 0;
	int final = bomb.size() - 1;

	if (final == 0)
	{
		string answer;
		for (int i = 0; i < s.size(); i++) {
			if (s[i] != bomb[0]) answer.push_back(s[i]);
		}
		if (answer.empty()) cout << "FRULA" << '\n';
		else cout << answer << '\n';
	}
	else {
		for (int i = 0; i < s.size(); i++)
		{
			if (s[i] == bomb[index]) {
				if (index == final) {
					for (int i = 0; i < final; i++) stk.pop();
					if (stk.empty()) index = 0;
					else index = stk.top().second + 1;
				}
				else {
					stk.push(make_pair(s[i], index++));
				}
			}
			else {
				index = 0;
				if (s[i] == bomb[index]) {
					stk.push(make_pair(s[i], index++));
				}
				else stk.push(make_pair(s[i], -1));
			}
		}
		if (stk.empty()) cout << "FRULA" << '\n';
		else {
			vector<char> v;
			while (!stk.empty()) {
				v.push_back(stk.top().first);
				stk.pop();
			}
			for (int i = v.size() - 1; i >= 0; i--) printf("%c", v[i]);
		}
	}
}