[Python] Programmers 불량 사용자 (2019 카카오 개발자 겨울 인턴)

풀이

 이번 문제에서 고려했어야했던 포인트는 두 가지로, 첫 번째는 후보 조합을 구하는 것과 두 번째는 조합 중 중복을 제외해야하는 것이다. 이렇게 복잡하게 풀 문제는 아니었는데, 깔끔한 알고리즘을 떠오르지 않았다.

후보 조합을 찾는 것은 2 step으로 구성되어있다. '*'로 치환되어있는 banned_id 들이 될 수 있는 후보를 먼저 dict형식으로 찾아놓은 후, DFS를 통해서 생성할 수 있는 모든 조합을 찾는다. 첫 번째 step에서 중요한 점은 banned_id의 후보를 dict 형식으로 저장할 때 id를 저장하는 것이 아닌 user_id의 위치를 저장한다. 이는 이후 중복체크할 때 사용된다. 조합을 찾을 때는 이미 선택한 id는 중복되서 들어갈 수 없으니 이미 앞에서 다를 banned_id로 선정된 경우는 제외하고 선정한다. 

ans = []

def compstr(user_id, banned_id):
    if len(user_id)!=len(banned_id):
        return False
    
    for a,b in zip(user_id, banned_id):
        if b == '*':
            continue       
        if a != b:
            return False
        
    return True
            
def cal(selected):
    temp = 0
    global ans
    for s in selected:
        temp += (1 << s)
    
    ans += [temp]
    return 

def DFS(candid, banned_id, selected):
    if len(banned_id) == 0:
        cal(selected)
        return 
    bid = banned_id[0]
    for c in candid[bid]:
        if c not in selected:
            DFS(candid, banned_id[1:], selected + [c])
    return

def solution(user_id, banned_id):
    candid = dict()
    for bid in banned_id:
        candid[bid] = []
        for i, uid in enumerate(user_id):
            if compstr(uid, bid):
                candid[bid] += [i]
                
    DFS(candid, banned_id, [])

    
    return len(set(ans))