[c++/프로그래머스] 불량 사용자

문제 링크

불량 사용자

풀이

DFS로 푸는 문제

1. 먼저 밴 아이디와 유저 아이디가 일치한다면 밴 아이디 인덱스에 맞춰 유저 아이디를 push_back 한다.
   1-1. 일치하는지 검사하는 함수 check는 일단 밴 아이디(a)와 유저 아이디(b) 길이가 맞지 않으면 false, a[i]가 *이라면 b[i]는 검사할 필요가 없고, 아니라면 같은지 확인해서 return 한다.
   1-2. 예가 밑과 같이 이루어질 때
   user_id -> frodo fradi crodo abc123 frodoc
banned_id -> fr*d* abc1**
   그렇게 만들어진 vector v는,
   v -> {frodo fradi} {abc123}
   이 될 것이다.
2. 이제 dfs를 이용하는데 재귀를 사용한다.
   2-1. list는 그래프 깊이 idx의 vector이고 list를 하나씩 체크하는데,
   있는 아이디를 또 넣지 않기 위한 set에 그 아이디(list[i])가 없다면 insert 해서 다시 재귀를 돌린다.(그 깊이의 노드 탐색은 완료했으니 다음 노드 탐색)
   2-2. 그렇게 탐색하다가 idx==v.size()가 되면 마지막 깊이까지 탐색했다는 뜻이므로 allSet에 넣고 return 한다.
3. allSet은 같은 경우의 수가 중복될 수 있어서 사용하는 set이다.
   두번째나 세번째 예 같이 밴 아이디가 중복되는 경우에서 사용한다.

코드

#include <string>
#include <vector>
#include <set>
#include <iostream>

using namespace std;

vector<vector<string>> v;

set<set<string>> allSet;

void DFS(set<string> id, int idx)
{
    if(idx==v.size())
    {
        allSet.insert(id);
        return;
    }
    vector<string> list = v[idx];
    
    for(int i=0;i<list.size();i++)
    {
        if(id.find(list[i])!=id.end()) continue; // set에 이미 아이디가 있다면
        set<string> tmp = id;
        tmp.insert(list[i]);
        
        DFS(tmp, idx+1);
    }
    
    return;
}

bool check(string a, string b)
{
    if(a.size()!=b.size()) return false;
    for(int i=0;i<a.size();i++)
    {
        if(a[i]=='*') continue;
        if(a[i]!=b[i]) return false;
    }
    return true;
}

int solution(vector<string> user_id, vector<string> banned_id) {
    for(int i=0;i<banned_id.size();i++)
    {
        vector<string> tmp;
        for(int j=0;j<user_id.size();j++)
        {
            if(check(banned_id[i], user_id[j])) // 일치한다면
            {
                tmp.push_back(user_id[j]);
            }
        }
        v.push_back(tmp);
    }
    
    set<string> s;
    DFS(s, 0);

    return allSet.size();
}