• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    해결됨

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

23.11.28 21:03 작성 조회수 97

0

선생님 안녕하세요. 우선 강의 잘 듣고 있습니다. 감사합니다.

다름이 아니라, 제가 5-B 문제를 선생님 풀이방법과 거의 유사하게 풀었는데 답안 제출 시 시간초과가 발생하여 질문 드리게 되었습니다.

1차 for문을 돌면서 original 문자열을 1개씩 순회하며, 새로운 문자열을 만들어가며 폭탄 문자열 길이 이상이 되었을 때 뒤에서부터 폭탄 문자열과 비교하며 같으면 erase()로 제거하는 방식까지는 선생님 풀이방법과 똑같습니다.

다른 부분은 뒤에서부터 폭탄 문자열과 비교하는 부분입니다. 선생님께서는 substr을 만들어서 == 비교연산자를 통해 폭탄문자열을 찾으셨는데요. 저의 경우, 아래 링크로 공유드린 코드와 같이 check() 라는 함수를 만들었고, 거기서 폭탄문자열 길이만큼 for문을 돌며 폭탄문자열이 존재하는지 체크를 한 후, 존재하면 erase()를 하도록하였습니다.

즉, 폭탄문자열 체크하는 부분만 다르며, 선생님 풀이처럼 substr 후 == 비교연산자로 체크하는 부분으로 수정을 하면 시간초과없이 통과가 되는데, 제가 작성한 check() 함수를 사용하면 시간초과가 납니다.

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

http://boj.kr/fa122a7d9a5e456388da1c04be04ff69

 

감사합니다.

답변 1

답변을 작성해보세요.

1

큰돌님의 프로필

큰돌

지식공유자

23.11.29 08:04

안녕하세요 ㅎㅎ

코드 잘 짜셨네요.

 

제가 생각했을 때는 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점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.


dhhan0430님의 프로필

dhhan0430

질문자

23.11.29 09:43

선생님 안녕하세요. 답변 정말 감사드리고, 시간 초과에 대한 이유를 정확히 알게 되었습니다.

항상 좋은 강의해주시고 답변도 정성스럽게 달아주셔서 감사드립니다.

감사합니다!