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

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

프로그래머스

 

 백트래킹 조합문제이다. 

 

문제를 해석하는 것이 가장 중요하고 해석만 하면 조합을 구할 줄 알면 쉽게 풀 수 있다.

 

나중에 한번 더 풀어보면 좋을 문제

 

#include <string>
#include <vector>
#include <map>
#include <iostream>
#include <set>
using namespace std;
vector<string> user, ban_user;

set<string> answerset;

bool check[8] = {false,};
bool banCheck(string id, string ban){
    if(id.size() != ban.size()) return false;
    for(int i = 0; i < id.size(); i++){
        if(ban[i] != '*'){
            if(id[i] != ban[i]) return false;
        }
    }
    //cout << id << endl;
    return true;
}

void dfs(int idx){
    if(idx == ban_user.size()){
        string tmp = "";
        for(int i = 0; i < user.size(); i++){
            if(check[i])
                tmp += (i + '0');
        }
        //cout << tmp << endl;
        answerset.insert(tmp);
        return;
    }
    
    for(int i = 0; i < user.size(); i++) {
        if(check[i]) continue;
        if(banCheck(user[i], ban_user[idx])){
            check[i] = true;
            dfs(idx + 1);
            check[i] = false;
        }
    }
}

int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 0;
    user = user_id;
    ban_user = banned_id;
    
    dfs(0);
    
    return answerset.size();
}