두 가지 풀이법이 있다
순열 답안 코드
from itertools import permutations
def check(case, banned_id):
for i in range(len(banned_id)):
if len(case[i])!=len(banned_id[i]):
return False
for j in range(len(banned_id[i])):
if banned_id[i][j]=='*':
continue
if case[i][j]!=banned_id[i][j]:
return False
return True
def solution(user_id, banned_id):
answer = []
for cases in permutations(user_id, len(banned_id)):
if check(cases, banned_id):
cases = set(cases)
if cases not in answer:
answer.append(cases)
return len(answer)user_id의 최대 길이가 8, 각 원소의 최대 길이도 8이기 때문에 banned_id와 각각 확인해보는 순열도 시간상 가능하다
DFS 답안 코드
'질문하기' 탭을 봤을 때 dfs로도 가능하다는 말을 보고, 몇 분의 코드를 빌려 dfs를 작성해봤다. 이상하게 한 분이 코드가 모두 이해가 되는게 아니라서 여러명의 코드를 참고했다
def solution(user_id, banned_id):
answer= []
possible_dict = {}
#불량 사용자별로 가능한 아이디 list 만들기
for b in banned_id:
possible_dict[b] = []
for b in banned_id:
for u in user_id:
if len(u)!=len(b):
continue
flag = True
for i in range(len(b)):
if b[i]=='*':
continue
if b[i]!=u[i]:
flag = False
break
if flag and u not in possible_dict[b]:
possible_dict[b].append(u)
def dfs(case, count):
nonlocal answer
#불량 사용자를 전부 확인했으면
if count==len(banned_id):
if set(case) not in answer:
answer.append(set(case))
return
#현재 확인할 불량 사용자
now = banned_id[count]
for i in range(len(possible_dict[now])):
#불량 사용자와 매칭이 가능한 아이디가 case안에 있는지 확인
if possible_dict[now][i] in case:
continue
case.append(possible_dict[now][i])
dfs(case, count+1)
case.pop()
dfs([],0)
return len(answer)마스킹된 아이디 별로 가능한 아이디를 lis로 만들어준 다음, dict를 돌면서 가능한 경우의 수를 dfs로 모두 확인한다 (answer를 set으로 뒀다가 해시가 불가능하다는 이상한 에러가 자꾸 떠서 그거때문에 애먹었다..)
참고한 분들
데이터를 공부하고 있습니다