알고리즘86 :: 프로그래머스_불량사용자

package programmers;
 
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
 
public class 불량사용자 {
 
    static ArrayList<String> al;
    static Map<String, Integer> ma = new HashMap<>();
    static int ans = 0;
    static void DFS(String[] user_id, String[] banned_id, int[] visit, int nn, int index, int index2, int target) {
        if(target == nn) {
            
            Collections.sort(al);
            String newS = "";
            for(int i=0; i<al.size(); i++) {
                newS+=al.get(i);
            }
            
            if(ma.get(newS)!=null)
                return ;
            else {
                ma.put(newS, 1);
                ans+=1;
            }
            
        }else {
            for(int i=0; i<user_id.length; i++) {
                if(visit[i]!=0) continue;
                visit[i] = 1;
                    for(int z=index; z<banned_id.length; z++) {
                        boolean find = false;
                        if(user_id[i].length() != banned_id[z].length()) continue;
                        for(int k=0; k<banned_id[z].length(); k++) {
                            if(user_id[i].charAt(k)==banned_id[z].charAt(k) ||
                                banned_id[z].charAt(k) == '*'    
                                    ) {
                                ;
                            }else {
                                find = true;
                            }
                        }
                        if(find == false) {
                            //visit[z] = 1;
                            al.add(user_id[i]);
                            DFS(user_id, banned_id, visit, nn+1, z+1, i+1, target);
                            al.remove(user_id[i]);
                            //visit[z] = 0;
                        }    
                }
                visit[i] = 0;
            }
        }
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        String[] user_id = {
                "frodo", "fradi", "crodo", "abc123", "frodoc"
        };
        String[] banned_id = {
                "fr*d*", "*rodo", "******", "******"
        };
        
        int[] visit = new int[user_id.length];
        al = new ArrayList<>();
        DFS(user_id, banned_id, visit, 0, 0, 0,banned_id.length);
        
        System.out.println(ans);
    }
 
}
 

 

접근했을 때 DFS 안에 3중 포문을 돌려서 해결했다. 

user_id 와 banned_id 각각에 대해서 중복을 체크했지만 

user_id에서 전체를 다 봐야했기 때문에 index+1 로 인자를 넘겨서 DFS 함수를 만들수는 없었다. 때문에, visit 처리 해서 순열로 처리했고 어쩔 수 없이 나오는 중복 순열에 대해서는 String 으로 뭉쳐서 Hash 처리를 했다.