[Lv.3] 불량 사용자

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    static Set<Set<String>> result=new HashSet<>();
    static String[] users;
    static String[] bans;

    public int solution(String[] user_id, String[] banned_id) {
        users=user_id.clone();
        bans=banned_id.clone();
        dfs(0,new HashSet<>());
        return result.size();
    }
   
    public boolean checkBanned(String target, String banned) {
        if(target.length()!=banned.length())
            return false;
        for (int i=0;i<target.length();i++){
            char c= target.charAt(i);
            char ban=banned.charAt(i);
            if(c!=ban&&ban!='*'){
                return false;
            }
        }
        return true;
    }

    public void dfs(int depth,Set<String> set){
        if(depth==bans.length){
            result.add(set);
            return;
        }
        for (int i = 0; i < users.length; i++) {
            if(!set.contains(users[i])&&checkBanned(users[i],bans[depth])){
                set.add(users[i]);
                dfs(depth+1,new HashSet<>(set));
                set.remove(users[i]);
            }
        }

    }

}

---

처음엔 Map과 순열, 조합 그리고 dfs로 풀어보려 했지만 쉽지 않았다.. 중복되지 않는 keyid들을 다시 배열로 만들어 반복문을 돌리고 뭐 visited 체크하며 해보았으나 코드스멜이 너무 심해졌고 이런식으로는 풀면 안될 것 같다는 생각이 들어 전부 지워버렸다.

 

그후 천천히 생각을 해봐도 깔끔하게 짤 방법이 안 떠올라 결국 여기를 참고했다.

 

풀이는 생각보다 간단했다.

중복을 저장하지 않는 HashSet의 특성을 이용하여 밴 아이디 순서대로 dfs를 진행하고 각 단계에서 해당 밴 아이디에 해당하는 유저 아이디를 찾아보고 해당 유저 아이디가 이미 밴 목록에 없는 경우 밴 목록에 추가한 후 다음 step으로 넘어가는 것을 반복한다.

최종적으로 depth가 밴 아이디 크기와 같아지면 일치하는 case를 찾게된다. 여기서 중요한건 찾았다고 그냥 answer++을 하는게 아닌 해당 목록을 set에 저장한다.

왜냐하면, 이런 방식의 dfs를 사용하면 입출력 예 3번같이 똑같은 밴 아이디가 중복된 경우에 대해 다른 케이스로 두 번 add하게 된다.

즉, answer가 2 증가한다. (하지만, 생각해보면 (abc123,frodoc)은 (frodoc,abc123)과 같다)

따라서, 똑같은걸 추가해도 되도록 set에 추가한다 (중복되어 저장되지 않으니까.)

 

이렇게 쭉 검사를 마치고 나면 결국 result Set에는 중복되지 않는 조합의 case들만 들어있게 된다.

 

따라서, result의 크기가 정답이 되는 것이다..!

 

역시 코드를 길고 더럽게 짜야하는 문제는 없는 것 같다.

앞으로 꾸준히 차분하고 쉽게 생각하려 노력해야 겠다.

(계속 생각하면서 머리속에서 꼬여버리는 것 같다..)