[2019 카카오 겨울인턴] 불량사용자 (JAVA)

도움을 받아 문제 해결함..

 

1. 각각 banned_id에 해당하는 candidate 등록

 

1) banned_id의 "*" 을 정규식으로 사용가능한 "."으로 바꿔주기

-> replace이용

2) 길이 같을 때 정규식이 일치한다면 candidate 넣기

-> matches 메소드 이용

 

2. 모든 candidate에 대해 dfs로 탐색해주기

package kakao;

import java.util.*;

public class bannUser {
	static Integer[][] candidate;
	static boolean[] visit;
	 static int solution(String[] user_id, String[] banned_id) {
	        int answer = 0;
	        candidate=new Integer[banned_id.length][user_id.length];
	        visit=new boolean[9];
	        
	        for(int i=0;i<banned_id.length;i++) {
	        	banned_id[i]=banned_id[i].replace("*", ".");
	        	int idx=0;
	        	for(int j=0;j<user_id.length;j++) {
	        		if(user_id[j].matches(banned_id[i])) candidate[i][idx++]=j; 
	        	}
	        }
	        
	        dfs(banned_id,user_id,0);
	        answer=result.size();
	        System.out.println(result);
	        return answer;
	    }
	 
	 static HashSet<Integer> set;
	 static ArrayList<Integer> list=new ArrayList<>();
	 static ArrayList<HashSet> result=new ArrayList<>();
	 
	 static void dfs(String[] banned_id,String[] user_id,int idx) {
		 if(idx==banned_id.length) {
			 set=new HashSet<>();
			 set.addAll(list);
			 
			 //list의 중복 체크
			 boolean flag=true;
			 for(HashSet str: result) {
				 if(str.containsAll(list)) flag=false;
			 }
			 if(flag) result.add(set);
			 return;
		 }
		 
		 for(int i=0;i<candidate[idx].length && candidate[idx][i]!=null;i++) {
			 if(!visit[candidate[idx][i]]) {
			 list.add(candidate[idx][i]);
			 visit[candidate[idx][i]]=true;
			 dfs(banned_id,user_id,idx+1);
			 visit[candidate[idx][i]]=false;
			 list.remove(idx);}
		 }
	 }
	 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String[] user_id= {"frodo", "fradi", "crodo", "abc123", "frodoc"};
		String[] banned_id= {"*rodo", "*rodo", "******"};
		solution(user_id,banned_id);
	}

}