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

---

1. 전체 코드

from collections import defaultdict


def solution(user_id, banned_id):
    def check(b, u):
        for i, j in zip(b, u):
            if i == '*':
                continue
            if i != j:
                return False
        return True

    def dfs(idx, path):
        # 백트래킹 조건1
        if len(path) == len(banned_id):
            path.sort()
            s = ''.join(path)
            if s not in result:
                result.append(s)
            return
            
        # 인덱스 에러 방지를 위해 초과된 idx 접근 불가(위의 return이 이 역할)
        #if idx >= len(banned_id):
        #     return
        
        for j in d[banned_id[idx]]:
            # 백트래킹 조건2
            if j not in path:
                dfs(idx + 1, path + [j])
    set_ban = set(list(banned_id))
    d = defaultdict(list)
    for ban in set_ban:
        for user in user_id:
            if len(ban) == len(user) and check(ban, user):
                d[ban].append(user)
            else:
                continue
    result = []
    dfs(0, [])
    return len(result)

---

2.후기

이 문제가 어렵다면 Letter Combinations of a Phone Number 이 문제 먼저 풀어보자. 접근 방식은 동일하다.