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

불량 사용자 목록에 글자 일부 가려져있고, 전체 사용자 ID가 있을 때 나올 수 있는 불량 사용자 경우의 수를 구하는 문제이다.

Python

from collections import defaultdict

def solution(user_id, banned_id):
    answer = 0
    pos = defaultdict(list)
    
    for bidx, bid in enumerate(banned_id):
        for idx, uid in enumerate(user_id):
            if (chk_banned(uid, bid)):
                pos[bidx].append(idx)
    ans = set()
    dfs(0, pos, set(), ans)
    return len(ans)

def chk_banned(uid, bid):
    if len(uid) != len(bid):
        return False
    for i in range(len(uid)):
        if bid[i] == '*' or uid[i] == bid[i]:
            continue
        else:
            return False
    return True
    
def dfs(now, pos, used, ans):
    if now not in pos:
        u = list(used)
        u.sort()
        ans.add(tuple(u))
        return 
    for uid in pos[now]:
        if uid not in used:
            used.add(uid)
            dfs(now + 1, pos, used, ans)
            used.remove(uid)

먼저 uid와 bid를 점검하는 함수를 만들었다. 그래서 그것을 기반으로 각 banned_id에 적용가능한 uid를 딕셔너리로 저장했다.

그러고 나서 dfs함수를 통해서 banned_id의 index 순서대로 들어가면서 나올 수 있는 경우를 탐색했다.

문제의 조건 중에서 목록 순서 상관없이 아이디 내용이 동일하면 같은 것으로 처리한다고 했기에 마지막에 used 집합을 정렬된 튜플로 만들어서 ans 집합에 추가했다.

마지막으로 dfs가 끝나면 ans 집합의 길이를 반환했다.

---

예전같으면 solution 함수 안에 다 넣거나 dfs만 함수로 만들었을 텐데 라피신을 하고 나니까 함수가 너무 길어지지 않게 기능별로 함수를 쪼개는 습관이 생긴 것 같다. 앞으로 이런 방향으로 코드 짜야겠다.