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

코드

import java.util.*;
class Solution {
    static boolean []check;
    static String []user;
    static String []ban;
    static int userLen;
    static int banLen;
    static Set<List<Integer>> set=new HashSet<>();
    public int solution(String[] user_id, String[] banned_id) {
        userLen=user_id.length;
        banLen=banned_id.length;
        check=new boolean [userLen];
        user=user_id;
        ban=banned_id;

        dfs(0);

        return set.size();
    }
    public void dfs ( int banId){
        if(banId>=banLen){
            List<Integer> list=new ArrayList<>();
            for(int i=0; i<userLen; i++){
                if(check[i])
                    list.add(i);
            }
            set.add(list);

            return;
        }
        if(ban[banId].equals("")){
            dfs(banId+1);
            return;
        }

        for(int i=0; i<userLen; i++){
            if(!check[i]&&isBan(user[i], ban[banId])){
                check[i]=true;
                dfs(banId+1);
                check[i]=false;
            }
        }
    }

    public boolean isBan(String u, String b){
        if(u.length()!=b.length()) return false;
        for(int i=0; i<u.length(); i++){
            if(b.charAt(i) == '*') continue;
            else if(u.charAt(i)!=b.charAt(i)) return false;
        }
        return true;
    }

}

풀이

문자열의 길이가 8이고 배열의 길이도 8인것을 보아 모든 조합을 시도해 보는 문제임을 알 수 있다. 여기서 까다로운 점은 순서 상관없이 내용이 같은 밴유저 조합은 하나로 계산한다는 것이다. 따라서 밴유저 조합을 만든 다음, 그 조합이 중복되지 않도록 관리해야한다. 여기서는 list에 유저를 넣은 다음, 해당 유저 list가 중복으로 저장되지 않게 set에 저장한다.