[Programmers] 불량 사용자

제재 아이디 목록에 있는 이름과 사용자 목록에 있는 이름이 일치할 경우 제재 아이디로 분류하고, 이 때 나올 수 있는 제재 아이디 조합의 수를 구하는 문제이다.

문제 해결 전략
우선 vector에 제재 아이디 별로 일치하는 사용자 이름들을 집어 넣는다.

예를들어 사용자 이름에 "fradi", "frodo", "crodo" 가 있고, 제재 아이디로 "*rodo"가 있다면 여기 해당하는 이름에는 "frodo"와 "crodo"가 있게 되는 것이다.

그리고 이 vector에 대해 dfs를 적용한다.

dfs의 인자로는 해당 vector와 중복 여부를 잡아줄 set, 그리고 depth를 넘겨준다.

기존의 dfs에서 사용하던 visit여부를 활용하기 위해 set을 사용하였는데, 만약 다음 depth에 해당하는 vector의 이름들이 set에 존재하는 경우는 넘어가고 존재하지 않는 경우에만 dfs를 계속해 나가는 것이다.

그리고 depth가 banned_id의 size와 같게 되었다면 끝까지 탐색을 했다는 의미이므로 이 때의 set을 공통되는 set의 유무를 판단하기 위한 더 큰 set에 집어넣어 준다.

다 끝나면 제일 큰 set의 사이즈를 반환해 주면 된다.

코드

#include <string>
#include <vector>
#include <set>
using namespace std;
int si;
set<set<string>> ss;
void dfs(vector<string> v[], set<string> s, int depth){
    if(depth == si){
        ss.insert(s);
        return;
    }
    
    for(int i=0;i<v[depth].size();i++){
        if(s.find(v[depth][i]) == s.end()){
            s.insert(v[depth][i]);
            dfs(v,s,depth+1);
            s.erase(s.find(v[depth][i]));
        }
    }
}
int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 0;
    
    vector<string> v[9];
    
    si = banned_id.size();
    for(int i=0;i<banned_id.size();i++){
        for(int j=0;j<user_id.size();j++){
            if(banned_id[i].size() != user_id[j].size())
                continue;
            int flag = 0;
            for(int k=0;k<banned_id[i].size();k++){
                if(banned_id[i][k] == '*')
                    continue;
                if(banned_id[i][k] != user_id[j][k]){
                    flag = 1;
                    break;
                }
            }
            if(flag == 0)
                v[i].push_back(user_id[j]);
        }
    }
    
    set<string> s;
    for(int i=0;i<v[0].size();i++){
        s.insert(v[0][i]);
        dfs(v,s,1);
        s.erase(s.find(v[0][i]));
    }
    return answer = ss.size();
}

출처 : 프로그래머스 https://programmers.co.kr/learn/courses/30/lessons/64064