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

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

프로그래머스

 

 

해결 방법

1. 각 banned_id에 누가 후보가 될 수 있는지를 저장하는 targets 변수를 선언한다 . vector<vector<int>> targets 이다.targets[i] 는 i번째 banned_id[i] 에 매칭되는 사용자의 index를 저장한다( ex.  [0,1,2] )
2. 이 targets를 가지고, 가능한 조합들을 찾는다. goSearch() 부분을 보면된다. 각 열에서 한개씩 뽑아서, 가능한 조합 set<int> 를 만든다. 
3. 전체 조합의 개수는 combinations.size() 가 된다. 만약 [0,1,2] 와 [1,0,2] 가 뽑혔을 경우, 두 경우는 동일한 경우로 간주해야하기 때문에 set<set<int>>를 사용해야한다.

 

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

using namespace std;

set<set<int>> combinations;
vector<vector<int>> targets;

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

void goSearch(set<int> users, int row){
    int sum =0;
    
    if(row >= targets.size()){
        combinations.insert(users);  
        return;
    } 
    
    for(int i=0 ; i<targets[row].size(); i++){
        if(users.find(targets[row][i]) != users.end())continue;
        users.insert(targets[row][i]);
        goSearch(users, row+1);
        users.erase(targets[row][i]);
    }
}
int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 0;
    
    //포맷별로 가능한 유저를 넣음.
    targets.resize(banned_id.size(),vector<int>());
    for(int i =0; i<banned_id.size(); i++){
        for(int j=0; j<user_id.size(); j++){
            if(isMatch(user_id[j],banned_id[i])) targets[i].push_back(j);
        }
    }
    
    goSearch(set<int>(),0);
    
    return combinations.size();
}