[프로그래머스 Level 3] 불량 사용자 - JavaScript

🔗 문제 링크

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

프로그래머스

✏️ 풀이

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;
}

먼저 banned_id의 형식에 맞는 아이디를 user_id에서 찾기 위해서 banned_id의 문자열을 활용하여 정규표현식 배열을 생성하였다.

 

그 다음 DFS를 통해 banned_id의 길이만큼 user_id에서 정규표현식과 일치하는 아이디를 하나씩 선택하기를 반복한다. selected 배열을 통해 선택 여부를 저장하기 때문에 여러 정규표현식에 모두 해당하는 아이디를 중복 선택하는 것을 방지할 수 있다. 

 

banned_id의 길이만큼 user_id에서 아이디를 모두 선택했다면 set에 추가한다. 이 때, 정렬과 join의 구분자를 통해 같은 아이디를 다른 순서로 고른 것에 대해서 중복으로 세는 것을 방지할 수 있다.

 

이렇게 해서 DFS를 통해 가능한 모든 경우를 탐색하고, 그 결과에 대해서도 순서만 다르고 같은 아이디가 담긴 목록의 중복까지 모두 제거한 상태의 개수(set.size)를 반환하면 정답이다.