프로그래머스: 불량 사용자 - javascript(정규식, 완전탐색(dfs), 중복제거 Set)

문제 출처 

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

프로그래머스

문제 풀이 힌트 

 

정답 풀이 코드 

function solution(user_id, banned_id) {
    const regex = banned_id.map(id => new RegExp(`^${id.replaceAll('*','.')}$`)) //*을 .으로 바꿔줌으로써 .자리에 모든 문자가 올 수 있다. 
    let selected = new Array(user_id.length).fill(false) //해당 user_id를 선택했는지 체크하는 함수 
    
    const set = new Set() // [a아이디, b아이디] 이나 [b아이디, a아이디]는 같으니 중복을 걸러준다. 
    
    function dfs(L, arr){ //L은 banned_id 의 idx가 된다. 
        if(L === banned_id.length){
            arr.sort((a,b) => { //정렬 먼저 해주고 
                if(a < b) return -1
            })
            set.add(arr.join(',')) //문자열로 만들어준 다음에 set에 push를 한다. (set에 배열 그대로 넣으면 중복 체크 안해줌) 
        }else{
            for(let i=0; i<user_id.length; i++){ //해당 banned_id에 알맞는 user_id를 찾아볼 것임. 
                     if(selected[i]) continue //하지만 이미 user_id가 다른 banned_id에 들어갔다면 그 아이디는 pass
                          if(user_id[i].match(regex[L])){ //banned_id에 맞는 user_id일 때 
                           selected[i] = true //해당 user_id 썼다고 체크. 
                           dfs(L+1, [...arr, user_id[i]]) //선택한 user_id 들 배열에 계속 누적 
                           selected[i] = false;              
                }
       
            }
        }
    }
    dfs(0,[])
    return set.size
}

 

Only 풀이 코드 

function solution(user_id, banned_id) {
    const regex = banned_id.map(id => new RegExp(`^${id.replaceAll('*','.')}$`))
    let selected = new Array(user_id.length).fill(false)
    const set = new Set()
    function dfs(L, arr){
        if(L === banned_id.length){
            arr.sort((a,b) => {
                if(a < b) return -1
            })
            set.add(arr.join(','))
        }else{
            for(let i=0; i<user_id.length; i++){
                     if(selected[i]) continue
                          if(user_id[i].match(regex[L])){
                           selected[i] = true 
                           dfs(L+1, [...arr, user_id[i]])
                           selected[i] = false;              
                }
       
            }
        }
    }
    dfs(0,[])
    return set.size
}

 

 

내가 푼 코드

function solution(user_id, banned_id) {
     let all_arr = []
     let n = banned_id.length
     
   for(let i=0; i<banned_id.length; i++){
       let regex = banned_id[i].replace(/\*/g,'\.')
       let arr = []; 
       let len = banned_id[i].length
       for(let user of user_id){
           if(user.match(regex) && user.length === len) arr.push(user)
       }
       all_arr.push(arr)
       
   }
    
 let set_answer = new Set(); 
      function dfs(L, select){
           if(L === n){
               let set = new Set([...select])
               if(set.size === n){
                   set_answer.add(select.sort((a,b) => {
                       if(a < b) return -1
                   }).join(''))
               }
           }else{
               for(let i=0; i<all_arr[L].length; i++){
                   dfs(L+1,[...select, all_arr[L][i]] )
               }
           }         
       }
    dfs(0, [])
    return set_answer.size; 
}