[프로그래머스] 불량 사용자(Python)

1. 요약

전체 아이디 사용자 목록과 불량 사용자 목록을 매핑할 때 나올 수 있는 경우의 수를 구하는 문제. 불량 사용자 목록에 있는 사용자 ID는 개인정보 보호를 위해 1자리 이상 *처리 되어있다.
제제 아이디 목록들을 구했을 때, 이들이 나열된 순서와 관계없이 아이디 목록 내용이 동일하다면 같은 것으로 처리하여 하나로 취급한다.

2. 아이디어

permutation(user_id, banned_id의 개수)를 이용해서 나올 수 있는 경우들을 구한다. 조합대신 순열을 사용했던 이유는 구현을 할 때, 각 경우에 대해, 2중 반복문을 돌렸기 때문이다. TC 3번을 예시로 설명하면, 만약 조합을 사용할 경우, 가능한 수는 5가지로 아래와 같다.

frodo, fradi, crodo, abc123 -> 매핑 실패
frodo, fradi, crodo, frodoc -> 매핑 실패
frodo, fradi, abc123, frodoc -> 매핑 성공
frodo, crodo, abc123, frodoc -> 매핑 성공
fradi, crodo, abc123, frodoc -> 매핑 성공


내가 작성한 코드의 경우, 조합으로 구현하면 경우 3번이 매핑이 실패한다. 왜냐하면, frodo가 fr*d*에 매핑되기 때문이다. 따라서 순열로 이용해서 풀었고, 매핑 결과가 중복되지 않는 것만 카운팅했다. 딕셔너리를 이용하여 banned_id의 원소가 이미 매핑이 완료됐는지 체크했다. 이 때, banned_id가 중복 될 수 있으므로 인덱스도 딕셔너리의 키로 사용했다.(i.e. key값이 (banned_id의 원소, 인덱스)로 튜플 형태이다)

3. 코드

from collections import defaultdict
from itertools import permutations

black_dict = {}
flag = False
possibles = [[]]

def solve(k, th, uid, bid):
    global black_dict, answer, flag
    if k == len(uid):
        if (bid, th) not in black_dict.keys(): 
            flag = True
            black_dict[(bid, th)] = uid
        return 
    
    if uid[k] == bid[k] or bid[k] == '*': solve(k+1, th, uid, bid)

def solution(user_id, banned_id):
    global black_dict, flag, answer_list
    answer = 0
    banned_id_len = len(banned_id)

    for uids in tuple(permutations(user_id, banned_id_len)):
        black_dict = {}
        for uid in uids:
            flag = False
            for i, bid in enumerate(banned_id):
                if len(uid) == len(bid): solve(0, i, uid, bid)
                if flag: break

        if len(black_dict.keys()) == banned_id_len:
            tmp = [value for value in black_dict.values()]
            tmp.sort()
            if tmp not in possibles:
                answer += 1
                possibles.append(tmp)
                
    return answer