5-B erase(), substr() 시간복잡도 질문드립니다.

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

5-B : erase()를 이용한 풀이

작성

896

수정됨

안녕하세요 선생님.선생님께서 푸신 코드가 시간복잡도가 통과되지 않을 것이라 생각하였는데 통과하여 질문드립니다.제가 알기로는 substr(), erase() 함수 모두 자르고 당기는 작업이 들어가서 O(n)의 시간복잡도가 걸린다고 알고 있는데, 반례로 문자열이 100만이 모두 같은 알파벳으로 aaa...라고 하고 폭발 문자열이 a라고 한다면 반복문을 100만번 돌면서 매번 substr()과 erase()를 해주게 되어 100만 * (O(n) + O(n)) 이 되어 시간복잡도가 넘어가는 것 아닌가요? 이 경우에 substr()과 erase()가 둘다 한개의 문자(a)만 체크하기 때문에 상수시간으로 취급하여 최대 200만이 되어 문제가 안 생기는 것 같기는 한데 뭔가 시간복잡도를 빡세게 잡는 문제가 나온다면 이러한 접근으로 erase()와 substr()을 사용한다면 시간초과가 날 수도 있지 않을까 하는 고민이 생겨서 질문드립니다! substr()과 erase()를 사용해도 시간복잡도 고려에 문제가 없을까요?

이 코드는 제가 find()와 erase()를 사용하여 푼 경우입니다. 이 경우에도 반복문을 돌리고 매번 find()와 erase()를 쓰는데, find()도 동일하게 O(n)이 걸리니까 로직이 선생님께서 푼 것과 동일하다고 판단하였는데, 아래 로직은 시간초과가 떴습니다.

#include<bits/stdc++.h>
using namespace std;
string s, a;

int main(){
    cin >> s >> a;    
    while(true){
        if(!s.size()){cout << "FRULA" << '\n'; return 0;}
        int flag = s.find(a);
        if(flag != string::npos){
            s.erase(flag, a.size());
        }
        else
            break;
    }
    cout << s << '\n';
}

c++코딩-테스트

답변 2

큰돌

지식공유자

안녕하세요 덕용님 ㅎㅎ

가장 큰 차이는 바로 이부분인데요.

    while(true){
        if(!s.size()){cout << "FRULA" << '\n'; return 0;}
        int flag = s.find(a);

덕용님은 매번 find를 하며 문자열 전체를 찾습니다. (while - true 하면서요.)

이렇게 되면 많은 시간복잡도 -> 시간초과가 나는 것 같습니다.

자세하게 설명드리면요.

find()는 한번찾을 때 -> 보통은 O(N)의 시간복잡도를 가지는데요. N은 s.size()

최악의 경우 M(찾으려는 문자열의 길이)를 계속해서 빼는 것을 더하게 되겠죠..?

이 경우 N+(N−M)+(N−2M)+…N + (N - M) ...가 되어 결국 O(N^2)이 됩니다. (등차수열의 합 공식)

큰 문자열 순회와 같은 로직의 경우 보통은 단 한번 순회한다는 생각으로.

효율적으로 구축할 생각을 하시는게 좋습니다.

    for(char a : S){
        ret += a;
        if(ret.size() >= T.size() && ret.substr(ret.size() - T.size(), T.size()) == T){

반면, 저는 for루프 한번으로 문자열 전체를 순회하면서 fin()가 아닌 부분 문자열 substr을 기반으로 비교해서 로직을 진행하는 것을 볼 수 있습니다.

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

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

감사합니다.

강사 큰돌 올림.

ddragon

질문자

감사합니다 선생님!

큰돌

지식공유자

덕용님 답변이 수정되었습니다. 참고부탁드립니다.

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴이에요.

substr()과 erase() 함수의 시간 복잡도는 모두 O(n)입니다. 하지만, 이는 함수가 “모든” 문자열에 대해 작업을 하는 경우의 시간 복잡도입니다. 실제로 사용되는 문자열의 길이가 매우 크거나 함수가 반복적으로 호출되는 경우에는 시간 복잡도에 영향을 주지 않을 수도 있습니다.

예를 들어, 반례로 문자열이 100만 개의 ‘a’로 이루어진 문자열이고 폭발 문자열이 ‘a’인 경우라면, substr()과 erase() 함수는 한번 호출할 때마다 하나의 문자열만을 체크하므로 상수 시간으로 처리될 수 있습니다. 따라서 시간 복잡도는 O(n) * (O(1) + O(1)) = O(n)으로 처리됩니다. 이 경우 시간 초과가 발생하지 않을 것입니다.

하지만, 단일 문자열 체크가 아닌 다른 작업이 필요한 경우(예: 특정 문자열의 패턴 매칭)에는 시간 복잡도에 영향을 줄 수 있습니다. 이러한 경우에는 다른 알고리즘을 사용해야 할 수도 있습니다. 따라서, 시간 복잡도를 빡세게 잡는 문제가 있다면 substr()과 erase() 함수를 사용한 접근이 시간 초과를 일으킬 수도 있으니 다른 알고리즘을 찾아보는 것이 좋습니다.

find()와 erase() 함수를 사용한 경우도 마찬가지로, 문자열의 길이와 반복 호출 여부에 따라 시간 복잡도가 달라질 수 있습니다. find()의 경우에도 문자열의 길이에 비례하는 작업을 수행하므로, 시간 복잡도는 O(n)입니다.

따라서, substr()과 erase() 함수를 사용해도 시간 복잡도 고려에 문제가 없을 것입니다. 하지만 실제 사용하는 문제에 맞게 알고리즘을 선택하고, 시간적인 측면에서 최적화할 필요가 있다면 다른 알고리즘을 고려해보는 것이 좋습니다.

더 궁금한 점이 있으면 언제든지 물어보세요. 즐거운 공부되시길 바라요!

인프런 커뮤니티 질문&답변

5-B erase(), substr() 시간복잡도 질문드립니다.