[프로그래머스] L3 불량 사용자 / 2019 카카오 겨울 인턴십 (Java)

카카오

[프로그래머스] L3 불량 사용자 / 2019 카카오 겨울 인턴십

[풀이]

 

import java.util.*;
class Solution {
    static List<Integer> list = new ArrayList<Integer>();
    static Set<String> answer = new HashSet<String>();
    static boolean[] visit;
    public static int solution(String[] user_id, String[] banned_id) {
        visit = new boolean[user_id.length];
        dfs(0, user_id, banned_id);
        return answer.size();
    }
    static void dfs(int idx, String[] user_id, String[] banned_id){
        if(list.size()==banned_id.length){
            List<Integer> temp = new ArrayList<Integer>();
            for(int i=0; i<list.size(); i++)
                temp.add(list.get(i));
            Collections.sort(temp);
            String s = "";
            for(int i=0; i<temp.size(); i++)
                s += Integer.toString(temp.get(i));
            if(!answer.contains(s))
                answer.add(s);
            return;
        }
        
        for(int i=0; i<user_id.length; i++){
            String uid = user_id[i];
            String bid = banned_id[idx];
            if(visit[i] || (uid.length()!=bid.length())) continue;
            if(!isBanned(uid, bid)) continue;
            visit[i] = true;
            list.add(i);
            dfs(idx+1, user_id, banned_id);
            list.remove(list.size()-1);
            visit[i] = false;
        }
    }
    static boolean isBanned(String uid, String bid){
        int size = uid.length();
        for(int i=0; i<size; i++){
            if(bid.charAt(i)=='*') continue;
            if(uid.charAt(i)!=bid.charAt(i)) return false;
        }
        return true;
    }
}