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

--문제--

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

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

--문제접근--

처음에 문제를 봤을 때 조합을 통해서 풀어보는 것을 생각하였습니다. 

고려해야할 점들은 불량사용자들에 해당 될 수 있는 ID들을 모두 추출하는 과정이 필요하는것이였고, 이렇게 추출한 ID들을 어떻게 조합을 고려할 것인가 였습니다. 

저는 조합을 그대로 적용하여 풀었는데 조합을 한 이후 중복을 어떻게 해결할지 고민하였는데 이에 대한 해결법은 Hash를 사용하여 해결하였습니다.

 

--코드--

package Level3;

import java.awt.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;

public class 불량사용자 {
	static ArrayList<Integer>[] Combination;
	static boolean[] CheckCombination;
	static HashSet<String> answer;
	public static void main(String[] args) {
		String[] user_id= {"frodo", "fradi", "crodo", "abc123", "frodoc"};
		String[] banned_id= {"fr*d*", "abc1**"};
		System.out.println(solution(user_id,banned_id));
	}
	private static int solution(String[] user_id, String[] banned_id) {
		answer=new HashSet<>();
		int ban_length=banned_id.length;
		int user_length=user_id.length;
		CheckCombination=new boolean[user_length];
		Combination=new ArrayList[ban_length];
		for(int i=0;i<ban_length;i++) {
			Combination[i]=new ArrayList<Integer>();
		}
		for(int i=0;i<ban_length;i++) {
			int banIdLength=banned_id[i].length();
			for(int j=0;j<user_length;j++) {
				if(banIdLength!=user_id[j].length())continue;
				boolean CheckSuccess=true;
				for(int k=0;k<banIdLength;k++) {
					if(banned_id[i].charAt(k)=='*')continue;
					if(banned_id[i].charAt(k)!=user_id[j].charAt(k)) {
						CheckSuccess=false;
						break;
					}
				}
				if(CheckSuccess) {
					Combination[i].add(j);
				}
			}
		}
		DFS(0,ban_length,0,banned_id);
		
		return answer.size();
		
	}
	private static void DFS(int idx, int Goal,int start, String[] banned_id) {
		if(idx==Goal) {
			String temp="";
			for(int i=0;i<CheckCombination.length;i++) {
				if(CheckCombination[i])temp+=i;
			}
			answer.add(temp);
			return;
		}
		for(int j=0;j<Combination[idx].size();j++) {
			int temp_index=Combination[idx].get(j);
			if(!CheckCombination[temp_index]) {
				CheckCombination[temp_index]=true;
				DFS(idx+1,Goal,start+1,banned_id);
				CheckCombination[temp_index]=false;
			}
		}
		
	}

}