[c++] 백준 알고리즘 9935 문자열 폭발

 

 

백준 알고리즘 9935번 문제는 쉽게 접근하면 너무나도 쉽고, 

어렵게 접근하면 너무나도 어렵다.

 

저번주에는 하루종일 풀었는데도 못풀었고,

오늘 다시 시도했을 땐 3분 만에 풀었다.

 

확실한 건, 스택을 활용하면 아주 쉽게 풀린다는 것이다.

 

 

문제 링크

 

9935번: 문자열 폭발

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

 

문제 분류 

문자열(string) 클래스

스택

자료구조

 

문제 해석

input은 두 줄이다.

첫번째 줄 제시 문자열에서 

두번째 줄 폭발 문자열을 모두 찾아 제거하면 된다.

폭발문자열이 제거된 이후에 남아있는 폭발문자열도 거듭 제거해야한다.

처음 시도에는 폭발문자열이 모두 사라질 때 까지 루프를 돌렸는데, 이렇게 접근하면 당연히 시간초과가 날 수 밖에 없었다.

두 번째 시도에서는 제시 문자열을 순회하며 폭발문자열도 함께 순회를 했고, 폭발 문자열의 end 에 도달하면 제시 문자열을 폭발문자열만큼 삭제하였다. iterator 접근법을 취한 것인데, 삭제 후 iterator의 위치를 재조정해야하기때문에 여간 까다로운 일이 아니었다. 또한 aaaaaa/aa 입력과 같은 동일문자 반복 입력 케이스에서 오답이 났다.

 

오늘 세번째 시도에서는 stack 자료구조를 아주잘 활용하였다.

정답 문자열 스택을 하나 만들고,

제시 문자열을 한 글자씩 ans_str에 push한다.

마지막 n개 글자가 폭발문자열과 동일하면 n개 pop_back한다.

이 과정을 반복하였다.

시간초과 없이 깔끔히 통과하였다!

 

나의 코드

//
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

#include <string>
#include <algorithm>
#include <stack>
using namespace std;
int n, m;

#define MAXN 1000000
string mystr;
string explode_str;
int len;

bool ends_with_expl(const std::string& str) {
	if (len > str.size() || len != explode_str.size())return false;
	return str.substr(str.size() - len, len) == explode_str;
}


int main(void)
{
    
	cin >> mystr;
	cin >> explode_str;

	len = explode_str.size();
	string ans_str;

	string::iterator exp_iter = explode_str.begin();
	for (string::iterator iter = mystr.begin(); iter != mystr.end(); ++iter) {
		ans_str.push_back(*iter);
		if (ends_with_expl(ans_str)) {
			for (int i = 0; i < len; i++) ans_str.pop_back();
		}	
	}


	if( ans_str.empty()) cout << "FRULA";
	else cout << ans_str << "\n";

	return 0;
}