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

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

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

[ 문제풀이 ]

모든 banned_id에 대해서 가능한 user_id를 구해준 후 중복을 제외하고 만들 수 있는 조합의 개수를 구해주면 된다.

import java.util.*;

class Solution {
    
    List<Integer>[] list;
    Set<Integer> set;
    Set<String> ans;
    int answer, ul, bl;
    
    public int solution(String[] user_id, String[] banned_id) {
    	ul = user_id.length;
    	bl = banned_id.length;
        list = new ArrayList[bl];
        
        for (int i = 0; i < bl; ++i) {
            list[i] = new ArrayList<>();
            for (int j = 0; j < ul; ++j) {
                if (banned_id[i].length() != user_id[j].length()) continue;
                
                boolean vaild = false;
                for (int k = 0; k < user_id[j].length(); ++k) {
                    if (banned_id[i].charAt(k) == '*') continue;
                    if (banned_id[i].charAt(k) != user_id[j].charAt(k)) {
                        vaild = true;
                        break;
                    }
                }
                
                if (!vaild) list[i].add(j);
            }
        }
        
        set = new HashSet<>();
        ans = new HashSet<>();
        dfs(0);
        
        return answer;
    }
    
    public void dfs(int depth) {
        if (depth == bl) {
            StringBuilder sb = new StringBuilder();
            for (int n : set) {
                sb.append(n);
            }
            if (!ans.contains(sb.toString())) {
                ans.add(sb.toString());
                answer++;
            }
            return;
        }
        
        for (int s : list[depth]) {
            if (!set.contains(s)) {
                set.add(s);
                dfs(depth + 1);
                set.remove(s);
            }
        }
    }
}