[프로그래머스] 불량 사용자 (C++)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/64064

아이디어1

user id와 banned id가 같은 경우 true인 행렬 만들기

• 예제 1의 경우
  • "fr*d*"와 같은 경우가 0, 1번
  • "abc1**"와 같은 경우가 3번

아이디어 2

DFS와 Set을 통해서 경우의 수 추려내기

• 각 행에서 true인 것을 하나씩 고르기
• DFS로 각 행에서 하나씩 고른 모든 경우의 수 찾기
• shift 연산자를 통해서 각 index값으로 flag를 만들어서 선택된 index들에 대한 수를 만들어서 Set에 넣고 알아서 중복 처리

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

#include <iostream>

using namespace std;

bool CheckName(const string& uid, const string& bid)
{
    if (uid.length() != bid.length())
        return false;
    
    for (int i = 0; i < uid.size(); ++i)
    {
        if (uid[i] != bid[i] && bid[i] != '*')
            return false;
    }
    
    return true;    
}

void DFS(const vector<vector<bool>>& mat, set<int>& s, int start,
         int num)
{
    if (start >= mat.size())
    {
        s.insert(num);
        return;
    }
    
    for (int j = 0; j < mat[0].size(); ++j)
    {
        if (mat[start][j] == true && (num & 1 << j) == 0)
        {
            DFS(mat, s, start + 1, num + (1 << j));
        }
    }
}

int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 0;
    
    vector<vector<bool>> mat(banned_id.size(), vector<bool>(user_id.size(), false));
    
    for (int i = 0; i < banned_id.size(); ++i)
    {
        for (int j = 0; j < user_id.size(); ++j)
        {
            if (CheckName(user_id[j], banned_id[i]) == true)
                mat[i][j] = true;
        }
    }
    
    set<int> s;
    
    DFS(mat, s, 0, 0);
    
    answer = s.size();
    
    return answer;
}