4-F 질문입니다

안녕하세요 동훈님 ㅎㅎ

void go(int depth,int st){
    if (depth > K){
       
        ret = max(ret,cal());

        return;
    }

    for (int i = st; i < 26; i++){
        if (check[i]) continue;

        check[i] = true;
        go(depth+1, i+1);
        check[i] = false;
    }
}

이코드는 2^26이 아니라 26!코드입니다. 매번 26, 25.. 이렇게 함수를 호출하고 있습니다.

int cal(){
    int cnt = 0;
    for (int i = 1; i <= N; i++){

        bool doit = true;
        for (char c : A[i]){
            if (!check[c-97]){
                doit = false;
                break;
            } 
        }
        if (doit) cnt++;
  
    }

    return cnt;
}

cal 같은 경우 기저사례에 있고 한번밖에 사용되지 않기 때문에 그닥 시간에 미치는 영향은 없습니다.

즉, 26!이 동훈님의 코드의 시간복잡도입니다.

26!은 403291461126605635584000000이라서 시간초과가 나는 것 같습니다.

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

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

감사합니다.

강사 큰돌 올림.

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