[프로그래머스][불량 사용자]-Lv.3

문제링크

🎃문제 설명

🎃예시

🎃제한사항

🎃접근방법

1. dfs를 통해 중복이 없는 모든 조합을 구한다.(순서 상관있음)
2. dfs를 통해 얻은 정보들을 Set을 통해 중복 제거한다(순서 상관없이 중복 제거)
   3 set의 size을 반환한다.

🎃코드

import java.util.*;
class Solution {
    static boolean[] userVisited;
    static boolean[] banVisited;
    static HashSet<HashSet<String>> set = new HashSet<>();
    public int solution(String[] user_id, String[] banned_id) {
        int answer = 0;
        
        userVisited = new boolean[user_id.length];
        banVisited = new boolean[user_id.length];
        HashSet<String> arr = new HashSet<>();
        dfs(0, user_id, banned_id, arr);
        answer = set.size();
        return answer;
    }
    static void dfs(int depth, String[] user_id, String[] banned_id, HashSet<String> arr){
        if(depth == banned_id.length){
            set.add(new HashSet<>(arr));
            return;
        }
        for(int i=0; i<user_id.length; i++){
            if(!userVisited[i]){
                if(check(user_id[i], banned_id[depth])){
                    userVisited[i] = true;
                    arr.add(user_id[i]);
                    dfs(depth+1, user_id, banned_id, arr);
                    arr.remove(user_id[i]);
                    userVisited[i] = false;
                }
            }    
        }
        
    } 
    static boolean check(String user, String ban){
        if(user.length() != ban.length()){ // 길이가 안맞으면 false
            return false;
        }
        for(int i=0; i<user.length(); i++){
            if(ban.charAt(i)=='*') continue;
            if(user.charAt(i) != ban.charAt(i)){
                return false;
            }
        }
        return true;
    }
}

🎃알고넘어가기

조합은 구했지만 순서에 따른 중복이 허용되지 않기 때문에 중복제거를 어떻게 해야하나 고민을 했습니다. 처음에는 List로 접근하고 하려했으나 코드가 별로인거 같아서 Set을 사용했습니다. set<String[]> 을 하려했으나 중복체크가 되지 않았습니다. 그래서 Set<Set> 을 사용하여 문제를 풀 수 있었습니다.