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

문제 출처 : https://www.acmicpc.net/problem/9935

9935번: 문자열 폭발

문제

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

• 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
• 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
• 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.

두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.

출력

첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.

알고리즘 분류

• 자료 구조
• 문자열
• 스택

풀이

두 번의 시간 초과를 겪은 후에 통과할 수 있었다.

find함수로 모든 폭발 문자열을 삭제하는 풀이(코드3)는 find함수를 많이 호출하게 돼서 시간 초과가 떴다.

시간을 단축시키기 위해서, 가장 바깥의 for문은 주어진 문자열의 시작부터 끝까지 모든 인덱스를 한 번씩만 탐색하면서,

string fire(폭발 문자열)의 마지막 문자 fire[fire.length()-1]이

string sen(문자열)의 현재 탐색 중인 문자 sen[i]와 같다면 sen[i]부터 sen[i-fire.length()+1]까지 fire의 역순과 같은지

확인하고, 삭제하는 방식으로 풀었다.

 

삭제할 때 string::erase 함수를 사용했는데(코드2), 시간 초과가 떴고, string::pop_back 함수를 사용하니 통과됐다.(코드1)

코드1과 코드2의 for문의 동작은 차이가 없으니, erase 함수보다 pop_back 함수로 문자를 제거하는 것이 더 효율적이다라는 결론이다.

코드1(통과)

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string str, fire, answer = "";
    cin >> str >> fire;
    int fireIdx = fire.length()-1;
    for (int i = 0; i < str.length(); i++) {
        answer += str[i];
        if (answer[answer.length()-1] == fire[fireIdx]) {
            if (answer.length() >= fire.length()) {
                int cnt = 1;
                for (int j = fireIdx - 1; j >= 0; j--) {
                    if (answer[answer.length()-1 - (fireIdx - j)] != fire[j])
                        break;
                    cnt++;
                }
                if (cnt == fire.length()) {
                    //sen.erase(i - fire.length() + 1, fire.length());
                    for (int b = 0; b < fire.length(); b++) {
                        answer.pop_back();
                    }
                    //i = i - fire.length();
                }
            }

        }
    }
    if (answer.empty())
        cout << "FRULA" << '\n';
    else
    cout << answer << '\n';

        return 0;

}

코드2(시간 초과)

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string sen, fire;
    cin >> sen >> fire;
    int fireIdx = fire.length()-1;
    for (int i = 0; i < sen.length(); i++) {
        if (sen[i] == fire[fireIdx]) {
            if (i >= fire.length()-1) {
                int cnt = 1;
                for (int j = fireIdx - 1; j >= 0; j--) {
                    if (sen[i - (fireIdx - j)] == fire[j]) {
                        cnt++;
                    }
                }
                if (cnt == fire.length()) {
                    sen.erase(i - fire.length() + 1, fire.length());
                    i =i- fire.length();
                }
            }

        }
    }
    if (sen.empty())
        cout << "FRULA" << '\n';
    else
    cout << sen << '\n';

        return 0;

}

코드3(시간 초과)

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string sen, fire;
    cin >> sen >> fire;
    while (sen.find(fire) != string::npos) {
        //cout << sen.find(fire) << ' ' << sen << '\n';
        //sen.replace(sen.find(fire),fire.length(), "");
        sen.erase(sen.find(fire), fire.length());
    }
    if (sen.empty())
        cout << "FRULA" << '\n';
    else
    cout << sen << '\n';

        return 0;

}