문제 링크

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

문제 설명

• 유저 아이디 리스트, 불량 사용자 리스트가 주어짐
• 불량 사용자 리스트는 하나 이상의 *로 가려져 있음
• 가능한 모든 경우의 수 리턴

풀이

• 백트래킹으로 모든 경우의 수 탐색
• 각 노드를 탐색할 때마다 가능한지 조건 삽입

코드

def solution(user_id, banned_id):
    result = set()
    selected = [False] * len(user_id)
    dfs(user_id, banned_id, selected, result, 0)
    return len(result)


def dfs(user_id, banned_id, selected, result, start):
    if start == len(banned_id):
        result.add(get_result(user_id, selected))
        return
    for i in range(len(user_id)):
        if not selected[i]:
            if possible(user_id[i], banned_id[start]):
                selected[i] = True
                dfs(user_id, banned_id, selected, result, start + 1)
                selected[i] = False


def possible(original, encoded):
    if len(original) != len(encoded):
        return False
    for i in range(len(original)):
        if encoded[i] == '*':
            continue
        if original[i] != encoded[i]:
            return False
    return True


def get_result(user_id, selected):
    result = []
    for i in range(len(user_id)):
        if selected[i]:
            result.append(user_id[i])
    return tuple(sorted(result))