[프로그래머스] 불량 사용자 풀이

 


1. 문제

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

2. 풀이

  • 불량 아이디 별로 가능한 user id 를 확인합니다.
  • 구한 아이디들을 dfs 를 이용하여 가능한 모든 경우의 수를 구합니다.
def solution(user_id, banned_id):
    ban_users = [[] for x in range(len(banned_id))]
    # 1. 각 불량 아이디 별로 가능한 user id 확인
    for b_idx, ban in enumerate(banned_id):
        for u_idx, user in enumerate(user_id):
            # 길이 다르면 넘어감
            if len(ban) != len(user):
                continue
            # 글자별로 확인해서 맞으면 후보에 넣음
            is_can = True
            for w_idx in range(len(ban)):
                if ban[w_idx] == '*':
                    continue
                elif ban[w_idx] != user[w_idx]:
                    is_can = False
                    break
            if is_can == True:
                ban_users[b_idx].append(u_idx)
                
    # 2. 가능한 모든 조합 확인
    answer = set()
    is_visited = [0] * len(user_id)

    def dfs(depth):
        if depth == len(banned_id):
            answer.add(''.join([str(x) for x in is_visited]))
            return

        for x in ban_users[depth]:
            if is_visited[x] == 1:
                continue
            is_visited[x] = 1
            dfs(depth + 1)
            is_visited[x] = 0
    
    dfs(0)
    return len(answer)