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

문제 출처 

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

프로그래머스

문제 풀이 힌트 

 

정답 풀이 코드 

function solution(user_id, banned_id) {
    const selected = Array(user_id.length).fill(false); //user_id를 선택했는지 체크하는 함수 
    const regex = banned_id.map(id => new RegExp(`^${id.replaceAll('*', '.')}$`)); //*을 .으로 바꾸고, 완전히 일치하는지 확인하는 정규식 표현으로 바꿈.(그냥 암기해라) 
    const set = new Set(); //중복되는 거 뺄 예정
    
    //banned_id 길이만큼 일치하는 user_id 배열을 찾는것. 
    const dfs = (index = 0, arr = []) => { 
        if(index === banned_id.length){ //banned_id를 만족하는 조합을 찾았을 때 
            set.add(arr.sort().join(',')); // sort를 이용해서 순서를 일치시킴, join으로 하나의 문자열로 만들어서 중복된 문자열은 걸러지게 set에 add!
        }else{
            for(let i=0; i<user_id.length; i++){ //user_id들을 반복문 돌린다. 
                if(selected[i]){ //이미 선택된 user_id라면 pass
                    continue; 
                }
                if(user_id[i].match(regex[index])){ //만약 해당 user_id 가 banned_id에 일치하는게 있다면 
                    selected[i] = true; //해당 user_id 선택
                    dfs(index+1, [...arr, user_id[i]]); //다음 banned_id로 이동, 지금까지 조합 하나의 배열에 넣기
                    selected[i] = false; //user_id 선택 취소 푸는것. 
                }
            }
        }
    }; 
    dfs(); 
    return set.size //set의 size는 길이를 말한다. 
}

 

Only 풀이 코드 

function solution(user_id, banned_id) {
    const selected = Array(user_id.length).fill(false); 
    const regex = banned_id.map(id => new RegExp(`^${id.replaceAll('*', '.')}$`)); 

    const set = new Set(); 
    
    const dfs = (index = 0, arr = []) => {
        if(index === banned_id.length){
            set.add(arr.sort().join(',')); 
        }else{
            for(let i=0; i<user_id.length; i++){
                if(selected[i]){
                    continue; 
                }
                if(user_id[i].match(regex[index])){
                    selected[i] = true; 
                    dfs(index+1, [...arr, user_id[i]]); 
                    selected[i] = false; 
                }
            }
        }
    }; 
    dfs(); 
    return set.size
}

알고가는 ppoint 

나의 틀린 풀이 코드 

function checkId(banId, canId){
    if(banId.length !== canId.length) return false; 
    let point = 0; 
    while(point < banId.length){
        if(banId[point] === '*'){
              point++; 
        }else{
            if(banId[point] !== canId[point]){
                return false; 
            }
            point++; 
        }
    }
    return true; 
}

function solution(user_id, banned_id) {
    let obj = new Map(); 
    let cnt = 0; 
    for(let i=0; i<banned_id.length; i++){
        for(let j=0; j<user_id.length; j++){
           if(checkId(banned_id[i], user_id[j])){
               if(!obj.has(banned_id[i])){
                   obj.set(banned_id[i],[]);
                   obj.get(banned_id[i]).push(user_id[j])
               }else{
                   obj.get(banned_id[i]).push(user_id[j]); 
               }
           }
        }
    }
    console.log(obj, 'obj')
    //obj 돌면서 해당 키에 대한 값이 몇개인지?하고 계속 곱한 값을 return
    let answer = 1; 
    for(let value of obj.values()){
        answer *= value.length
    }
    return answer; 
}

//불량 사용자 목록 
//프로도에게 전달 
//사용자 아이디 중 일부 문자 *로 가려 
//-최소 하나 이상 
//응모자 아이디를 제대 아이디
//return 당첨에서 제외되어야 할 제재 아이디 목록은 몇가지 경우의 수가 가능한지 ?

//알파벳 소문자 , 숫자, * 로 이루어짐 
//불량 사용자 아이디

//완전탐색(dfs활용해보자.), 정규식, Set
//banned_id 돌면서 해당 banid에 만족하는 userid 있나 찾기
//- 함수: *의 idx를 기억해 그리고 point를 같이 ++ 하면서 idx 이외의 다른 것들이 다 같으면 true임 근데 처음부터 길이 세면 될 듯 
//그리고 cnt를 세면서 만약 banned_id 길이 만큼 된다면 
//set에다가 push 하기 
//return set 길이 

//Map으로 하니까 중복 키가 안돼서 안되고, 값은 중복돼서 안돼