프로그래머스 - 불량 사용자

해당 알고리즘 자료는 제가 직접 푼 것도 있지만 다른 분들의 풀이과의 비교를 통해 더 나은 알고리즘을 공부하기 위해 정리한 것들입니다.

프로그래머스 - 불량 사용자

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

풀이 1. (중급) - Dfs를 이용하여 banned_id와 일치한 경우를 Set에 저장한다.

import java.util.*;
class Solution {
    	static boolean [] visited;
	static int answer = 0;
	static TreeSet<String> set = new TreeSet<String>();
	static int [] list;
    static public int solution(String[] user_id, String[] banned_id) {
        visited = new boolean [user_id.length];
		list = new int [banned_id.length];
		dfs(0, 0, user_id, banned_id);
        return answer;
    }

    private static void dfs(int cnt, int start, String[] user_id, String[] banned_id) {
		if(cnt == banned_id.length) {
			Arrays.sort(list);
			String str = Arrays.toString(list);
			if(!set.contains(str)) {
				answer++;
				set.add(str);
			}
			return;
		}
		for (int i = start; i < user_id.length; i++) {
			for (int j = 0; j < banned_id.length; j++) {
				if(visited[j]) continue;
				boolean isPossible = true;
				if(banned_id[j].length() != user_id[i].length()) isPossible = false;
				else {
					for (int k = 0; k < banned_id[j].length(); k++) {
						if(banned_id[j].charAt(k) == '*') continue;
						if(banned_id[j].charAt(k) != user_id[i].charAt(k)) {
							isPossible = false;
							break;
						}
					}
				}
				if(isPossible) {
					visited[j] = true;
					list[cnt] = i;
					dfs(cnt+1, i+1, user_id, banned_id);
					visited[j] = false;
				}
			}
		}
	}
}

풀이 2. (고급) - Bit-Masking으로 점검한다.

import java.util.*;
class Solution {
   static HashSet<Integer> set = new HashSet<Integer>();
    int solution(String[] user_id, String[] banned_id) {
        match(user_id, banned_id, 0, 0);

        return set.size();
    }
    private static void match(String[] user, String[] banned, int bit, int idx) {
		if(idx == banned.length) {
			set.add(bit);
			return;
		}
		for (int i = 0; i < user.length; i++) {
			if((bit & (1 << i)) == 0) {
				if(banned[idx].length() == user[i].length() && check(user[i], banned[idx])) match(user, banned, bit | (1 << i), idx + 1);
			}
		}
	}
	private static boolean check(String u, String b) {
		for (int i = 0; i < u.length(); i++) {
			if(b.charAt(i) == '*') continue;
			if(u.charAt(i) != b.charAt(i)) return false;
		}
		return true;
	} 
}