🐤 코딩테스트 연습 - 불량 사용자

나의 풀이

class Solution {
    static HashSet<HashSet<String>> answer;
    public int solution(String[] user_id, String[] banned_id) {
        answer = new HashSet<>();

        dfs(new LinkedHashSet<>(), user_id, banned_id);

        return answer.size();
    }


    private static void dfs(HashSet<String> hs, String[] user_id, String[] banned_id) {
        if (hs.size() == banned_id.length) {
            if (isBanList(hs, banned_id)) {
                answer.add(new HashSet<>(hs));
            }
            return;
        }

        for (String userId : user_id) {
            if (hs.add(userId)) {
                dfs(hs, user_id, banned_id);
                hs.remove(userId);
            }
        }
    }


    private static boolean isBanList(HashSet<String> hs, String[] banned_id) {
        int idx = 0;
        for (String userID : hs) {
            String banID = banned_id[idx++];
            if (userID.length() != banID.length()) {
                return false;
            }
            for (int i = 0; i < banID.length(); i++) {
                if (banID.charAt(i) == '*') {
                    continue;
                }
                if (userID.charAt(i) != banID.charAt(i)) {
                    return false;
                }
            }
        }
        return true;
    }
}

접근 방식

• dfs를 이용한 조합을 이용하였다.(불량 사용자 리스트 갯수에 해당하는 아이디들 중 만들 수 있는 불량 사용자 리스트의 경우의 수)
• set을 이용한 중복 제거
• 1. isbannedList : 1. 아이디의 길이 2. 이 아닌 문자의 위치 3. 이라면 비교 넘기기로 구분한다.
• 2. isbannedList에서 검사를 완료하면 true를 return
• 3. 검사가 완료되고 불량 사용자 리스트크기만큼의 hashset이 생성하면 answer에 add

📝 후기

• dfs를 활용하지 못한 접근방식이 해결 하지 못한 원인
• 불량 사용자 리스트에서 *의 위치와 갯수에 따라 리스트 해당 판단 여부가 갈린다.