function solution(user_id, banned_id) {
  function dfs(user, idx, str, table) {
    if (idx === user.length) {
      if (table[str]) {
        table[str].push(user);
      } else {
        table[str] = [user];
      }
      return;
    }
    dfs(user, idx + 1, str + user[idx], table);
    dfs(user, idx + 1, str + "*", table);
  }

  function getList(user, idx, list, answer) {
    if (list.length === banned_id.length) {
      if (!answer.includes(list.sort().join(""))) {
        answer.push(list.join(""));
      }
      return;
    }
    for (let i = 0; i < user[idx].length; i++) {
      if (!list.includes(user[idx][i])) {
        getList(user, idx + 1, [...list, user[idx][i]], answer);
      }
    }
  }

  let table = {};
  let bannedIdList = [];
  let answer = [];

  user_id.forEach((user) => dfs(user, 0, "", table));
  for (let bannedUser of banned_id) {
    bannedIdList.push(table[bannedUser]);
  }
  getList(bannedIdList, 0, [], answer);
  return answer.length;
}

풀이

• 브루트포스
• dfs

1. user의 모든 제재 아이디 경우의 수를 table에 기록해 둔다.

"frodo"
"fradi"
table = {
 	"frodo" :["frodo"],
  	"*rodo" :["frodo"],
  	"**odo" :["frodo"],
  	....
  	"fr*d*" :["frodo","fradi"],
}

해당 역할은 함수 dfs()가 한다

function dfs(user, idx, str, table) {
  if (idx === user.length) {
    if (table[str]) {
      table[str].push(user);
    } else {
      table[str] = [user];
    }
    return;
  }
  dfs(user, idx + 1, str + user[idx], table);
  dfs(user, idx + 1, str + "*", table);
}

user_id.forEach((user) => dfs(user, 0, "", table));

2. banned_id 불량사용자 목록을 받아 제재아이디 후보를 작성한다

for (let bannedUser of banned_id) {
  	// bannedUser : "fr*d*"
    sanctionIdList.push(table[bannedUser]);
  	// table[bannedUser] : ["frodo","fradi"]
}

• sanction은 제재라는 뜻이라고 한다... (변수명 짓기 어렵다)

3. sanctionIdList에서 제재 아이디 목록을 작성한다
   3번 예제인 경우 다음과 같은 결과로 나온다

sanctionIdList = [
  [ 'frodo', 'fradi' ],  
  [ 'frodo', 'crodo' ],  
  [ 'abc123', 'frodoc' ], 
  [ 'abc123', 'frodoc' ]  
]

이제 해당 제재 아이디 목록에서 아이디를 하나씩 뽑아 순서와 상관 없는 조합을 하면 된다.

• 단, 아이디의 중복이 있으면 안된다
• 첫 번째 제자아이디 목록에서 "frodo"를 선택했으면 두번째 제재아이디 목록에서 "frodo"가아닌 "crodo"를 선택해야한다

나는 정석적인 조합 알고리즘 보다는 dfs와 문자열을 사용해 꼼수를 써서 구현했다.

function getList(user, idx, list, answer) {
  if (list.length === banned_id.length) {
    
    // 정렬후 문자열을 저장, 같은 목록인지 중복을 체크한다
    if (!answer.includes(list.sort().join(""))) {
      answer.push(list.join(""));
    }
    return;
  }
  for (let i = 0; i < user[idx].length; i++) {
    if (!list.includes(user[idx][i])) {
      getList(user, idx + 1, [...list, user[idx][i]], answer);
    }
  }
}

....

return answer.length; // 갯수를 return한다