백준 9935 (문자열 폭발) c++

문제

9935번: 문자열 폭발

문자열 주어지고 폭발 문자열이 주어집니다.

주어진 문자열에서 폭발 문자열이 발견되면 폭파됩니다. 

예를들어 주어진 문자열이 

mirkovC4nizCC44

위와 같고 폭발 문자열이

C4

라면 

마지막에는

mirkovniz

남습니다.

 

처음에 이 문제를 발견했을 때 생각했던게

먼저 KMP 알고리즘으로 문자열과 폭발 문자열이 같은 부분을 찾고

문자열을 폭발 문자열을 빼고 합치는 과정이 번거로웠습니다.

 

힌트를 얻고 보니 "스택" 자료구조를 사용해 해결하였습니다.

string st1;
cin >> st1;
string st2;
cin >> st2;

string s = "";

먼저 input 부분입니다.

st1에는 문자열이 들어가고 st2에는 폭발 문자열이 들어가게 됩니다.

s에는 이제 부터 폭발된 문자열이 들어갈 것입니다. 

s를 스택 형식처럼 생각해 줍니다.

해당 알고리즘의 핵심은 st1의 문자열을 s에 계속 넣어주다가 

폭발 문자열의 맨끝과 s문자열의 맨끝이 일치하면

폭발 문자열의 size만큼 검사해주는 것입니다.

 

맨 바깥 for 문을 보면 st1의 길이만큼 반복문을 돌립니다.

2번째 줄을 보면 s에다가 st1[i]를 넣어줍니다.

3번째 줄을 보면 s의 뒤 와 폭발문자열인 st2의 뒤와 같으면 이제 검사할 준비를 합니다.

5번째 줄을 보면 s의 size가  폭발 문자열보다 작으면 당연히 말이 안되므로 continue해줍니다.

6번째 줄을 보면 s를 폭발 문자열 만큼만 검사해주면 되기 때문에 s[s.size()-st2.size()+j] 를 하게 되면

s의 폭발 문자열의 길이만큼 검사할 수 있게 됩니다.

여기서 검사도중 문자열이 다르면 chk를 false 해주고 탈출합니다.

12번째 줄을 보면 chk라 여전히 truel이면 폭발 문자열이 발견된것이므로 폭발 문자열 만큼 pop 해줍니다.

if (s.empty())cout << "FRULA";	
else 
	cout << s;

마지막에 s가 empty이면 모든 문자열이 폭발 한것이므로 FRULA를 출력해주고

아니라면 s를 그대로 출력해주면 됩니다.

---

전체 코드입니다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
#include <tuple>
#define MAX 2100000000
#define inf LONG_MAX
#define big(a, b) a > b ? a : b
using namespace std;
using ll = long long;
using ull = unsigned long long;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    string st1;
    cin >> st1;
    string st2;
    cin >> st2;
 
    string s = "";
 
    for (int i = 0; i < st1.size(); i++) {
        s += st1[i];
        if (s.back() == st2.back()) {
            bool chk = true;
            if (s.size() < st2.size())continue;
            for (int j = 0; j < st2.size(); j++) {
                if (s[s.size() - st2.size() + j] != st2[j]) {
                    chk = false;
                    break;
                }
            }
            if (chk)
                for (int j = 0; j < st2.size(); j++)s.pop_back();
        }
    }
    if (s.empty())cout << "FRULA";    
    else 
        cout << s;
    
 
    return 0;
}