[프로그래머스] 2019 카카오 개발자 겨울 인턴십 - 불량 사용자(JavaScript)

📚 문제

이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견했습니다. 이런 응모자들을 따로 모아 불량 사용자라는 이름으로 목록을 만들어서 당첨 처리 시 제외하려고 합니다. 이 때 개인정보 보호를 위해 사용자 아이디 중 일부 문자를 * 문자를 사용하였습니다.
불량 사용자 목록에 매핑된 응모자 아이디를 제제 아이디라고 부르기로 했습니다.

예를 들어, 이벤트에 응모한 전체 사용자 아이디 목록이 다음과 같다면

응모자 아이디
frodo
fradi
crodo
abc123
frodoc

다음과 같이 불량 사용자 아이디 목록이 전달된 경우,

불량 사용자
fr*d*
abc1**

불량 사용자에 매핑되어 당첨에서 제외되어야 할 제제 아이디 목록은 다음과 같이 두 가지 경우가 있을 수 있습니다.

제제 아이디
frodo
abc123

제제 아이디
fradi
abc123

이 처럼 제제 아이디 목록은 몇가지 경우의 수가 가능한 지 return 하도록 solution 함수를 완성해주세요.

📖 풀이

let result = 0;
const memo = [];

function solution(user_id, banned_id) {
    const banned_list = banned_id.map(bannedId => bannedId.replace(/\*/g,'.'));
    const visit = [...user_id].fill(false);
    dfs(user_id, banned_list,0, 0, visit);
    return result;
}

function dfs(user_id, banned_id, idx, n, visit){
    const visited = [...visit];
    const regex = RegExp(`\^${banned_id[idx]}\$`);
    
    if(n === banned_id.length){
        const temp = [];
        visited.forEach((v,i) => v && temp.push(user_id[i]));
        
        let cnt = 0;
        memo.forEach(array => {
            let flag;
            for(let i = 0 ; i < temp.length ; i++){
                flag = array.some(element => element === temp[i]);
                if(!flag){
                    break;
                }
            }
            !flag && cnt++;
        });
        if(cnt === memo.length){
            memo.push(temp);
            result++;
        }
        return;
    }
    
    user_id.filter((id, index) => {
        if(regex.test(id)){
            if(!visited[index]){
                visited[index] = true;
                dfs(user_id, banned_id, idx+1, n+1, visited);
                visited[index] = false;
            }
        }
    });
}

생각보다 오래 걸렸던 문제입니다. 불량사용자의 아이디 목록을 가지고, 응모자 아이디를 매칭하여 제외를 시키는 문제였습니다.
불량사용자에 *은 문자 하나 이상을 포함하고 있는데 여기서 *을 .으로 만들어 하나 이상의 문자를 포함하도록 만드는 정규식을 이용해 응모자 목록에 매칭을 해야겠다고 생각했습니다. 매칭을 할 때, 하나하나 다 탐색을 해야하니 완전탐색 알고리즘을 사용해야하는데 그 중 깊이우선탐색(DFS)을 이용해 문제를 해결했습니다.

📃 링크

2019 카카오 개발자 겨울 인턴십 - 불량 사용자