문제 조건

input

• 문자열 배열 user_id, banned_id
  • 1 ≤ (begin, target).len ≤ 8

output

• 당첨에서 제외되어야 할 아이디 목록의 경우의 수

문제 해석

• 백트레킹으로 모든 경우의 수 추적
• 이때, 문제 조건에 의해 banned_id와 일치하는 케이스 찾기

코드

def solution(user_id, banned_id):
    answer_set = set()
    used = [False] * len(user_id)
    
    # user id와 ban id를 대조해서 재재 대상인지 판단
    def is_match(user, ban):
        if len(user) != len(ban):
            return False
            
        for i in range(len(ban)):
            if ban[i] == '*':
                continue
            if ban[i] != user[i]:
                return False

        return True

    def backtrack(path):
		    # 탈출 조건
        if len(path) == len(banned_id):
		        # 핵심: frozenset으로 변환해 중복을 제거해야함
		        # 일반적인 순열/조합으로는 문제 해결 불가능
		        # 반례가 모두 존재
		        # list는 가변 요소로 set의 요소로 활용할 수 없음
		        # frozenset으로 불변화 시킨 후 set에 넣어줘야 함
            answer_set.add(frozenset(path))
            return
        
        for i, u in enumerate(user_id):
            if not used[i] and is_match(u, banned_id[len(path)]):
                used[i] = True
                path.append(u)
                backtrack(path)
                path.pop()
                used[i] = False

    backtrack([])
    return len(answer_set)

# def solution(user_id, banned_id):
#     user_cases = []
#     combination = []    
#     visited = [False] * len(user_id)
    
    
#     # 조합을 이용하면, 3번 케이스에서 제재 아이디 fradi frodo abc123 frodoc 대응 실패
#     def combinations(start):
#         if len(combination) == len(banned_id):
#             user_cases.append(combination[:])
#             return 

#         for i in range(start, len(user_id)):
#             if not visited[i]:
#                 visited[i] = True
#                 combination.append(user_id[i])
#                 combinations(i+1)
#                 combination.pop()
#                 visited[i] = False
                
#     combinations(0)
#     banned_count = 0
    
#     for user_case in user_cases:
#         if isBanned(user_case, banned_id):
#             print(user_case, banned_id)
#             banned_count += 1
        
    
#     return banned_count

# def isBanned(user_case, banned_id):
#     for i in range(len(banned_id)):
        
#         if len(user_case[i]) != len(banned_id[i]):
#             return False
        
#         for j in range(len(banned_id[i])):
#             if banned_id[i][j] == '*':
#                 continue
#             if banned_id[i][j] != user_case[i][j]:
#                 return False

#     return True 

# def solution(user_id, banned_id):
#     user_cases = []
#     permutation = []    
#     visited = [False] * len(user_id)
    
# ['frodo', 'crodo', 'abc123', 'frodoc'] ['fr*d*', '*rodo', '******', '******']
# ['frodo', 'crodo', 'frodoc', 'abc123'] ['fr*d*', '*rodo', '******', '******']
# ['fradi', 'frodo', 'abc123', 'frodoc'] ['fr*d*', '*rodo', '******', '******']
# ['fradi', 'frodo', 'frodoc', 'abc123'] ['fr*d*', '*rodo', '******', '******']
# ['fradi', 'crodo', 'abc123', 'frodoc'] ['fr*d*', '*rodo', '******', '******']
# ['fradi', 'crodo', 'frodoc', 'abc123'] ['fr*d*', '*rodo', '******', '******']

#     def permutations():
#         if len(permutation) == len(banned_id):
#             user_cases.append(permutation[:])
#             return 

#         for i in range(len(user_id)):
#             if not visited[i]:
#                 visited[i] = True
#                 permutation.append(user_id[i])
#                 permutations()
#                 permutation.pop()
#                 visited[i] = False
                
#     permutations()
#     banned_count = 0
    
#     for user_case in user_cases:
#         if isBanned(user_case, banned_id):
#             print(user_case, banned_id)
#             banned_count += 1
        
    
#     return banned_count

# def isBanned(user_case, banned_id):
#     for i in range(len(banned_id)):
        
#         if len(user_case[i]) != len(banned_id[i]):
#             return False
        
#         for j in range(len(banned_id[i])):
#             if banned_id[i][j] == '*':
#                 continue
#             if banned_id[i][j] != user_case[i][j]:
#                 return False

#     return True