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

문제

접근방법

처음 봤을때 중복에 대한 생각을 Set을 생각하지 못해 접근이 어려웠었다.

 

1.  우선 Ban Id에 해당되는 아이디들을 구하여 ArrayList<>로 만든다.

2. DFS를 통해 1번에서 구한 아이디들을 BanID의 갯수만큼 하나씩 검색해서 HashSet에 넣는다.

2-1. 이 과정에서 중복을 피하기 위해 BanID의 사이즈와 Depth가 같도록 해서 종료조건을 설정한다.

답

import java.util.*;
import java.util.regex.Pattern;
class Solution {
    HashSet<HashSet<String>> result;
    ArrayList<ArrayList<String>> banUsers;
    
    public int solution(String[] user_id, String[] banned_id) {
        result = new HashSet<HashSet<String>>();
        banUsers = new ArrayList<ArrayList<String>>();
        
        for(String bannedId : banned_id){
            banUsers.add(getId(bannedId, user_id));
        }
        dfs(new HashSet<>(), 0);
        return result.size();
    }
    ArrayList<String> getId(String banId, String[] user_id){
        String pattern = banId.replace('*','.');
        ArrayList<String> list = new ArrayList<>();
        
        for(String uid : user_id){
            boolean isMatch = Pattern.matches(pattern, uid);
            
            if(isMatch) list.add(uid);
        }
        
        return list;
    }
    void dfs(HashSet<String> add, int depth){
        if(depth == banUsers.size()){
            result.add(new HashSet<>(add));
            return;
        }
        for(String userId : banUsers.get(depth)){
            if(!add.contains(userId)){
                add.add(userId);
                dfs(add, depth+1);
                add.remove(userId);
            }
        }
    }
}