글 읽기 - vector와 set의 시간 차이..?

liveinpeace 1년 전 0

두 코드에서 다른 부분들만 뽑아서 가져온 것입니다.

위의 코드는 set 컨테이너에서 iterator로 꺼내서 브루트포스를 한 것이고, 아래 코드는 vector 컨테이너에서 꺼내서 브루트포스를 한 것입니다.

그런데 위의 것은 시간초과가 뜨고 아래 것은 정답으로 되더군요.

제 IDE에서 돌렸을 때도 위의 코드는 확연히 느리더라고요.

set이 원래 그런건지, 아님 제가 뭔가 놓치고 있는건지 호기심에 질문 올립니다!

void dfs(int cur, int k){
    for(auto it=char_set.begin();it!=char_set.end(); it++){
        if(m[*it]>0)continue;
        m[*it]=k;
        dfs(cur+1, k-1);
        m[*it]=0;
    }
}
int main(){
    for(auto it=char_set.begin();it!=char_set.end(); it++){
        m[*it]=9;
        dfs(1, 8);
        m[*it]=0;
    }
}

--------------------------------------------------------------
    
void dfs(int cur, int k){
    for(int i=0;i<char_set.size();i++){
        if(m[char_set[i]]!=-1)continue;
        m[char_set[i]]=k;
        dfs(cur+1, k-1);
        m[char_set[i]]=-1;
    }
}
int main(){
    for(int i=0;i<char_set.size();i++){
        m[char_set[i]]=9;
        dfs(1, 8);
        m[char_set[i]]=-1;
    }
}