[Programmers]LV.3 불량 사용자

---

📝 기본 아이디어 

기본적인 불량 사용자 매핑으로는 풀 수 없는 문제이다. 

그 이유는 불량 사용자 중에 동일한 목록이 나올 수 있기에 중복 계산이 되어 크게 나올 수도 있기 때문이다.

 

또한 제한사항이 그렇게 크지 않아  DFS도 가능하다.

• 불량 리스트 별로 가능한 user_id 들을 저장
• HashSet을 이용해서 중복되는 루트를 거름
• 결과 또한 HashSet으로 저장하여 쉽게 결과 도출 

import java.util.*;

class Solution {
    Set<Set<String>> result = new HashSet<>();
    
    public int solution(String[] user_id, String[] banned_id) {
        List<List<String>> possibleBans = new ArrayList<>();
        
        // 각 banned_id에 대해 매칭 가능한 user_id 리스트 생성
        for (String ban : banned_id) {
            List<String> matchingUsers = new ArrayList<>();
            for (String user : user_id) {
                if (ban.length() == user.length() && valid(user, ban)) {
                    matchingUsers.add(user);
                }
            }
            possibleBans.add(matchingUsers);
        }
        
        findCombinations(possibleBans, new HashSet<>(), 0);
        
        return result.size();
    }
    
    private void findCombinations(List<List<String>> possibleBans, Set<String> selected, int index) {
        if (index == possibleBans.size()) {
            result.add(new HashSet<>(selected));
            return;
        }
        
        for (String user : possibleBans.get(index)) {
            if (!selected.contains(user)) {
                selected.add(user);
                findCombinations(possibleBans, selected, index + 1);
                selected.remove(user);
            }
        }
    }
    private boolean valid(String user, String ban) {
        for (int i = 0; i < user.length(); i++) {
            if (ban.charAt(i) != '*' && user.charAt(i) != ban.charAt(i)) {
                return false;
            }
        }
        return true;
    }
}