[프로그래머스] / [Level 3] / [Python] 불량 사용자

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

프로그래머스

---

ismatch 함수를 만들어 두 문자가 대체 가능한지 판단하도록 하였고,

알고리즘은 DFS를 사용하여 해결하였다.

visited 리스트를 만들어 현재 탐색하고 있는 user가 중복되지 않게 하였다.

def ismatch(a, b):
    if len(a) != len(b):
        return False
    
    for _a, _b in zip(a, b):
        if _a == '*' or _b == '*':
            continue
        elif _a == _b:
            continue
        else:
            return False
    else:
        return True
        
def solution(user_id, banned_id):
    answer = set()
        
    def bfs(b_idx, visited, user_id_list):
        nonlocal answer
        
        if b_idx == len(banned_id):
            answer.add(tuple(sorted(user_id_list)))
            return
        
        for u_idx in range(len(user_id)):                         
            if visited[u_idx] == False:
                if ismatch(user_id[u_idx], banned_id[b_idx]):
                    
                    visited[u_idx] = True                    
                    user_id_list.append(user_id[u_idx])

                    bfs(b_idx+1, visited, user_id_list)
                    
                    visited[u_idx] = False
                    user_id_list = user_id_list[:b_idx]
                    
    
    visited = [False for _ in range(len(user_id))]
    
    bfs(0, visited, [])
    
    return len(answer)

 

다른 사람 풀이

깔끔하다고 판단하여 추가해서 정리한다.

 

itertools 라이브러리의 product 함수를 사용하여 모든 경우의 수를 뽑아내고,

banned_id의 개수와 맞는 결과만 뽑아내는 방법이다.

from itertools import product

def ismatch(a, b):
    if len(a) != len(b):
        return False
    
    for _a, _b in zip(a, b):
        if _a == '*' or _b == '*':
            continue
        elif _a == _b:
            continue
        else:
            return False
    else:
        return True

def solution(user_id, banned_id):
    answer = set()

    result = [[] for _ in range(len(banned_id))]
    
    for i in range(len(banned_id)):
        for u in user_id:
            if ismatch(banned_id[i], u):
                result[i].append(u)
    
    result = list(map(set, product(*result)))
    
    for r in result:
        if len(r) == len(banned_id):
            answer.add(tuple(sorted(r)))

    return len(answer)