[Baekjoon] 9935번: 문자열 폭발

🥅 문제

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

 

🔍 설계

문자열의 반복문을 돌리면서, 폭발 문자열과 일치하는 부분 문자열이 만들어지면, 맨 위부터 폭발시켜야 하므로, 스택을 이용한다는 것은 쉽게 파악할 수 있었다.

 

폭발 문자열과 일치하면 현재 인덱스에서 폭발 문자열에서 일치한 인덱스를 save에 저장하고, 다음 탐색할 인덱스(cur_idx)를 1 증가시키면서 폭발 문자열의 길이와 일치하면 폭발시키는 방식으로 설계했다.

 

초기 설계에서의 문제점은 스택에 문자만 담았기 때문에 폭발하고 난 후, 다음 탐색할 인덱스를 폭발 문자열이 완성된 위치에서 폭발 문자열의 길이를 뺀 인덱스에서의 save 값과 같이 잘 못 구했었다. 하지만 이런 경우, 

 

abaabcdbcdcd

abcd

 

와 같이 중간에 두 번 이상 폭발이 이루어지는 경우에 올바르지 않다.

 

단순하게 스택에 문자와 그 문자의 위치를 같이 저장하고, 그 위치에서의 save값 + 1이 다음 탐색할 인덱스이다.

 

👊 풀이

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

string original, boom;
stack<pair<char, int>> s;
vector<int> save(1000000, -1);
int cur_idx = 0, temp_idx;

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);	
	cin >> original >> boom;
	int original_length = original.length();
	int boom_length = boom.length();
	for (int i = 0; i < original_length; i++) {
		s.push({ original[i], i });
		if (s.top().first == boom[cur_idx]) {
			save[i] = cur_idx;
			cur_idx += 1;
			if (cur_idx == boom_length) {
				for (int j = 0; j < boom_length; j++) {
					s.pop();
				}
				if (s.empty()) {
					cur_idx = 0;
				}
				else {
					cur_idx = save[s.top().second] + 1;
				}
				
			}
		}
		else {
			cur_idx = 0;
			if (s.top().first == boom[cur_idx]) {
				save[i] = cur_idx;
				cur_idx += 1;
			}
		}
	}

	string result = "";

	if (s.empty()) {
		cout << "FRULA" << "\n";
		return 0;
	}

	while (!s.empty()) {
		result += s.top().first;
		s.pop();
	}
	reverse(result.begin(), result.end());
	cout << result << "\n";

	return 0;
}