백준 - 문자열 폭발 (9935) [C++]

 이 문제는 스택을 이용해서 풀었다. 예전에 풀었다가 결국 못 풀었었는데, 이번에는 정답을 맞췄다. 스택을 pair에 대해 사용하였고, first는 문자, second는 다음 매칭되어야 할 인덱스를 저장했다. 구현은 비교적 쉽게 했는데, 계속 시간 초과가 났었다. 알고보니 이는 마지막에서 result = st.top().first + result 를 사용해서 reverse 함수 없이 바로 출력했었는데 이 방법이 O(N) 시간을 소요하게 된다고 한다. 매번 result에 O(N) 시간이 걸리므로 최악 O(N^2) 이 걸리게 되어 시간 초과가 발생하는 것이다. 그래서 result += st.top().first 를 사용하고 reverse 를 사용하면 총 O(N) 시간밖에 안 걸려 정답이 나오게 된다.

 

 

 

#include <iostream>
#include <string>
#include <stack>
#include <utility>
#include <algorithm>

using namespace std;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	string input;
	string exp;

	cin >> input;
	cin >> exp;

	stack<pair<char, int>> st;
	
	int size = input.size();
	int expSize = exp.size();

	for (int i = 0; i < size; i++) {
		char c = input[i];

		if (st.empty()) {
			if (exp[0] == c) {
				st.push({ c, 1 });
			}
			else {
				st.push({ c, -1 });
			}
		}
		else {
			if (st.top().second == -1) {
				if (exp[0] == c) {
					st.push({ c, 1 });
				}
				else {
					st.push({ c, -1 });
				}
			}
			else {
				if (exp[st.top().second] == c) {
					st.push({ c, st.top().second + 1 });
				}
				else if (exp[0] == c) {
					st.push({ c, 1 });
				}
				else {
					st.push({ c, -1 });
				}
			}
		}

		if (st.top().second == expSize) {
			for (int j = 0; j < expSize; j++) {
				st.pop();
			}
		}
	}

	if (st.empty()) {
		cout << "FRULA" << '\n';
	}
	else {
		string result = "";

		while (!st.empty()) {
			result += st.top().first;
			st.pop();
		}

		reverse(result.begin(), result.end());

		cout << result << '\n';
	}

	return 0;
}