문제 푼 날짜 : 2021-09-22

문제

문제 링크 : https://www.acmicpc.net/problem/9935

접근 및 풀이

문제를 보자마자 직관적으로 폭발 문자열을 find 함수로 계속 찾아주면서 erase 시키면 되겠다라고 생각했는데, 이렇게 하니 시간초과가 떴다...
문제점을 찾다가 폭발 문자열을 찾아주는 부분이 문제라고 생각했다.
find 함수는 원본 문자열의 길이가 m이고 그 속에서 찾고 싶은 패턴 문자열의 길이가 n일 때, O(mn)의 시간 복잡도를 갖기 때문에 이 부분을 아래와 같이 수정해주었다.

1. 문자열을 순서대로 탐색하면서 새로운 string 변수에 저장해준다.
2. 탐색된 문자가 폭발 문자열의 마지막 문자와 같으면 폭발 문자열의 길이만큼 그 위치에서 거꾸로 탐색해준다.
3. 폭발 문자열과 일치한다면 그 문자들을 pop해준다.

코드(시간초과)

// 백준 9935번 : 문자열 폭발
#include <iostream>

using namespace std;

int main() {
    string str, bomb;

    cin >> str >> bomb;

    while (true) {
        auto it = str.find(bomb);
        if (it == string::npos) {
            break;
        } else {
            str.erase(it, bomb.length());
        }
    }
    if (str.length() == 0) {
        cout << "FRULA";
    } else {
        cout << str;
    }
    return 0;
}

코드(통과)

// 백준 9935번 : 문자열 폭발
#include <iostream>
#include <stack>

using namespace std;

int main() {
    string str, bomb;
    string ret = "";

    cin >> str >> bomb;

    for (int i = 0; i < str.length(); i++) {
        int len = bomb.length();
        ret += str[i];

        if (ret[ret.length() - 1] == bomb.back()) {
            if (ret.length() - len >= 0) {
                int cnt = 0;
                for (int j = bomb.length() - 1; j >= 0; j--) { 
                    if (ret[ret.length() - (bomb.length() - j)] == bomb[j]) {
                        cnt++;
                    }
                }
                if (cnt == bomb.length()) {
                    for (int j = 0; j < cnt; j++) {
                        ret.pop_back();
                    }
                }
            }
        }
    }
    if (ret.length() == 0) {
        cout << "FRULA";
    } else {
        cout << ret;
    }
    return 0;
}

결과

피드백

과도한 라이브러리 함수 남용은 좋지 않은 결과를 낳을 수도 있다는 사실을 명심하자..