안녕하세요. 5-B 문제 시간복잡도 질문 드립니다.

안녕하세요 ㅎㅎ

코드 잘 짜셨네요.

제가 생각했을 때는 check()도 O(N)이고, == 비교연산자도 O(N)일 것으로 생각이 드는데 왜 check() 함수를 사용하면 시간초과가 나는지 이해가 안가서 질문드립니다. == 비교연산자가 O(N)이어도 문제 상에서 폭탄 문자열의 최대길이가 36 정도이기 때문에 시간초과가 발생하지 않았다고 생각을 했었고, 따라서 O(N)인 check() 함수도 시간초과가 발생하지 않을 것으로 생각했었습니다.

>> 네 맞습니다. 해당 시간복잡도는 수강생님이 생각하신 것과 동일하게 같습니다.

이렇게 한번 고쳐보시겠어요?

inline bool check(string &s, string &bomb) {
    int s_len = s.size(), bomb_len = bomb.size();

작은 문자열이라면 상관없지만 긴 문자열의 경우 call by reference로 넘기셔야 합니다.

이렇게 하시면 무사히 통과합니다.

http://boj.kr/7d48ac39a62449148a1c90c0a524c778

이 이유는 교안내의 다음 부분 참고 부탁드립니다.

참조에 의한 호출로 넘겨야 할 때

또한,

이렇게 수정한 코드 등으로 테스팅을 해봤는데요.

수강생님 코드가 제 코드보다 더 빠릅니다.

잘 짜셨습니다. ㅎㅎ

테스트 코드는 다음과 같습니다.

#include <bits/stdc++.h>
#include <chrono>

using namespace std;

string processA(string S, string T) {
    string ret;
    for (char a : S) {
        ret += a;
        if (ret.size() >= T.size() && ret.substr(ret.size() - T.size(), T.size()) == T) {
            ret.erase(ret.end() - T.size(), ret.end());
        }
    }
    return ret.empty() ? "FRULA" : ret;
}

bool checkB(const string &s, const string &bomb) {
    int s_len = s.size(), bomb_len = bomb.size();
    for (int i = 0; i < bomb_len; i++) {
        if (s[s_len - 1 - i] != bomb[bomb_len - 1 - i])
            return false;
    }
    return true;
}

string processB(string input, string bomb) {
    string res;
    int bomb_len = bomb.size();
    for (int i = 0; i < input.size(); i++) {
        res += input[i];
        if (res.size() >= bomb_len && checkB(res, bomb)) {
            res.erase(res.size() - bomb_len, bomb_len);
        }
    }
    return res.empty() ? "FRULA" : res;
}

int main() {
    string S, T;
    cin >> S >> T;

    auto start = chrono::high_resolution_clock::now();
    string resultA = processA(S, T);
    auto end = chrono::high_resolution_clock::now();
    chrono::duration<double, std::milli> elapsedA = end - start;
    cout << "Code A took " << elapsedA.count() << " ms\n";

    start = chrono::high_resolution_clock::now();
    string resultB = processB(S, T);
    end = chrono::high_resolution_clock::now();
    chrono::duration<double, std::milli> elapsedB = end - start;
    cout << "Code B took " << elapsedB.count() << " ms\n";
 
    cout << "Result of Code A: " << resultA << "\n";
    cout << "Result of Code B: " << resultB << "\n";

    return 0;
}

결과 : 어떤 TC의 경우.

Code A took 0.28879 ms

Code B took 0.07447 ms

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.