[프로그래머스][백트래킹][순열] 불량 사용자

불량 사용자

프로그래머스

 

• 풀이
  • 각 depth별 가능한 유저 result에 모음
  • 중복되지 않는 순열 만들기
  • 순열들을 모아 set으로 중복 없애기
    • 📍tuple(sorted(selected))
      • set에는 리스트가 들어갈 수 없기 때문에 sorted한 후 tuple
      • = 중복 없는 튜플 만들어짐

def solution(user_id, banned_id):
    answer = set()
    result=[]
    
    for bann in banned_id:
        tmp=set()
        for user in user_id:
            if len(bann)!=len(user):
                continue
            for b,u in zip(bann,user):
                if b=='*':
                    continue
                if b!=u:
                    break
            else:
                tmp.add(user)
        result.append(tmp)
    
    def dfs(depth, selected):
        nonlocal answer
        if depth == len(banned_id):
            answer.add(tuple(sorted(selected)))
            return
        
        for user in result[depth]:
            if user not in selected:
                selected.append(user)
                dfs(depth + 1, selected)
                selected.pop()
    dfs(0,[])

    return len(answer)