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

1. 2중 반복문을 돌려 banned_id에 매핑되는 user를 store 배열에 저장한다.

2. 저장한 배열을 이용해 가능한 모든 경우의 수를 구하기 위해 user_count 함수를 이용해 깊이 우선 탐색을 이용한다.

3. 모든 경우의 수를 저장한 total 배열을 정렬한 후 비교해 중복되는 값을 제외한 개수를 구한다.

#include <string>
#include <vector>
#include <map>
#include <algorithm>
 
using namespace std;
 
int MAX = 0;
map<string, bool> M;
vector<vector<string>> total;
vector<string> store[8];
vector<string> temp;
vector<string> temp_copy;
 
void user_count(int cur) {
    if (cur >= MAX) { 
        temp_copy = temp;
        sort(temp_copy.begin(), temp_copy.end());
        total.push_back(temp_copy);
        return; 
    }
    
    for (int i = 0; i < store[cur].size(); i++) {
        if (M[store[cur][i]]) { continue; }
        M[store[cur][i]] = true;
        temp.push_back(store[cur][i]);
        user_count(cur + 1);
        temp.pop_back();
        M[store[cur][i]] = false;
    }
}
 
int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 0;
    
    MAX = banned_id.size();
    for (int i = 0; i < banned_id.size(); i++) {
        for (string user: user_id) {
            if (user.length() != banned_id[i].length()) { continue; }
            int index = -1;
            while (++index < banned_id[i].length()) {
                if (user[index] != banned_id[i][index] && banned_id[i][index] != '*') { 
                    break; 
                }
                if (index + 1 == user.length()) {
                    store[i].push_back(user);
                }
            }
        }
    }
    
    user_count(0);
 
    sort(total.begin(), total.end());
    
    answer = 1;
    for (int i = 0; i < total.size() - 1; i++) {
        for (int j = 0; j < total[i].size(); j++) {
            if (total[i][j] != total[i + 1][j]) {
                answer++;
                break;
            }
        }
    }
    return answer;
}