(카카오)불량 사용자(문제22)

import java.util.*;
 
class Solution {
    private static boolean[] isUsed;
    private static Set<Set<Integer>> answerSet = new HashSet<>();//
 
    private static int ans = 0;
    //키는 밴 인덱스, 값은 밴될수 있는 유저아이디 인덱스 후보!
    private static Map<Integer,List<Integer>> map = new HashMap<>();
    public int solution(String[] user_id, String[] banned_id) {
        isUsed = new boolean[user_id.length];
        int banneIdCount = banned_id.length;
        for(int i=0;i<banneIdCount;i++){
            map.put(i,new ArrayList<>());
        }
        initMap(user_id,banned_id);
//         for(int i=0;i<banneIdCount;i++){
//             System.out.println(map.get(i));
            
//         }
        
        solve(0,banneIdCount,new HashSet<>());
        /*
        1. map을 채운다.
        2. 재귀를 쓰면될듯하다.
        3. 끝조건: 이미 쓰고있거나 depth만족하면 끝낸다. depth만족시 카운트를 업하면됨
           상태: 밴길이 즉 밴 인덱스를 가면되고 
        */
        return answerSet.size();
    }
    
    private static void solve(int size,int target,Set<Integer> chosen){
        if(size == target){
            answerSet.add(new HashSet<>(chosen)); // 조합 저장
            return;
        }
        //밴 목록에있는 후보녀석들 순회
        for(int userIdx : map.get(size)){
            if(isUsed[userIdx]) continue;
            isUsed[userIdx] = true;
            chosen.add(userIdx);
            
            solve(size+1,target,chosen);
            
            chosen.remove(userIdx);
            isUsed[userIdx] = false;
 
//             if(isUsed[userIdx]) continue;
//             isUsed[userIdx] = true;
//             solve(size+1,target,chosen);
//             isUsed[userIdx] = false;
        } 
    }
    
    private static void initMap(String[] userIds, String[] bannedIds){
        for(int i=0 ; i<bannedIds.length ; i++){
            String bannedId = bannedIds[i];
            for(int j=0 ; j<userIds.length ; j++){
                String userId = userIds[j];
                boolean isMatch = true;
                if(userId.length() != bannedId.length()) continue;
                for(int k=0;k<userId.length();k++){
                    if(bannedId.charAt(k) == '*') continue;
                    if(bannedId.charAt(k) != userId.charAt(k)){
                        isMatch = false;
                        break;
                    }
                }
                if(isMatch){
                    map.get(i).add(j);
                }
            }
        }
    }
}