(2019 카카오 인턴십) 불량 사용자

코딩테스트 연습 - 불량 사용자

 

#include <bits/stdc++.h>
using namespace std;
bool used[10];
int ret = 0;
set<string> S;
 
// 비교하는 함수
bool Compare(string a, string b){
 
    //길이가 틀리다면 다른 문자! 
    if(a.length() != b.length())  
        return false;
 
    // *이 아니고 서로 문자가 다르면 다른 문자!
    for(int i =0; i <a.length(); i++)
        if(a[i] != b[i] && b[i] != '*') 
            return false;
    return true;
}
 
void getResult(int idx, vector<string> user_id, vector<string> banned_id){
    if(idx == banned_id.size()){ // 기저조건
        string tmp;
        for(int i =0; i < user_id.size(); i++) 
            if(used[i]) tmp+= i+'0'; //인덱스 값을 문자열로 넣는다.
 
        // 사용 된 문자라면 함수를 종료한다.
        if(S.find(tmp) != S.end())  
            return; 
        
        // set에 tmp를 추가한다.
        S.insert(tmp);
        ret++;
        return;
    }
    for(int i = 0; i <user_id.size(); i++){
        //현재 사용 된 문자가 아니고 서로 같은 문자라면
        if(!used[i] && Compare(user_id[i], banned_id[idx])){
            used[i] = true;
            getResult(idx+1, user_id, banned_id);
            used[i] = false;
        }
    }
}
 
int solution(vector<string> user_id, vector<string> banned_id) {
    getResult(0, user_id, banned_id);
    return ret;
}
 
// int main(){
//     vector<string> user_id;
//     vector<string> banned_id;
 
//     user_id.push_back("frodo");
//     user_id.push_back("fradi");
//     user_id.push_back("crodo");
//     user_id.push_back("abc123");
//     user_id.push_back("frodoc");
 
//     banned_id.push_back("*rodo");
//     banned_id.push_back("*rodo");
//     banned_id.push_back("******");
 
//     cout<<solution(user_id, banned_id)<<endl;
//   //  cout<<S.size()<<endl;
// }

위의 코드에서는 S.find(tmp) 를 이용해서 만약 tmp 문자열이 이미 사용된 문자열이라면 함수가 종료 되도록 구현을 했습니다. 그리고 만약 사용 된 문자가 아니라면 S에 insert를 해주고 ret 값을 + 해줍니다. 

 

그리고 최종적으로 ret 값을 리턴해주어 결과 값을 얻는 방식인데요 

 

근데 사실 set 함수는 내부적으로 중복된 데이터 값을 지워버리기 때문에 

중복 데이터 처리

이 부분을 지워주시고 return 값을 S.size()로 하셔도 동일한 결과 값을 얻을 수 있습니다. 

이 문제의 경우 범위 자체가 8 밖에 되지않아 처리하기 어떻게 하셔도 상관 없지만 제 생각에 만약 범위가 더 커진다면 내부적으로 중복된 데이터 값을 처리하기 위해 더 많은 연산처리가 필요하지 않을까? 하는 생각이 듭니다. hash 테이블을 기반으로 하는거라 상관이 없나? 아무튼 ^^ 알고리즘 코딩은 항상 최악을 경우의 수에 두고 최고의 효율을 구현해야 한다는 것을 잊지맙시다!