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

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

코딩테스트 연습 - 불량 사용자

문자열을 파싱해서 제재 아이디에 해당하는 후보 리스트를 만들고, 조합을 구하는 문제이다

큰 문자열 연산이 필요 없어서 C로 구현해도 되겠다는 생각을 했다

 

나는 banned_id 배열을 탐색하면서 각각의 id에 매칭되는 user_id의 index를 담은 배열을 만들고,

해당 배열을 백트래킹으로 탐색하면서 중복되지 않는 경우의 수를 구해줬다.

user_id 배열의 최대 길이가 8이기 때문에 중복 여부는 bitmasking으로 구현했다.

def match(id, ban):
    if len(id)!=len(ban):
        return False
    
    for i in range(len(id)):
        if ban[i]!='*' and ban[i]!=id[i]:
            return False
    return True

def combination(candidate_id, dep, bs, check):
    if dep>=len(candidate_id):
        if check.get(bs)!=None: return 0
        check[bs]=True
        return 1
    
    cnt = 0
    for id in candidate_id[dep]:
        if bs&(1<<id)!=0: continue
        
        bs=bs^(1<<id)
        cnt += combination(candidate_id, dep+1, bs, check)
        bs=bs^(1<<id)
    
    return cnt
    

def solution(user_id, banned_id):
    answer = 0
    candidate_id = []
    
    for ban in banned_id:
        candidate_id.append([])
        for i in range(len(user_id)):
            if match(user_id[i], ban):
                candidate_id[-1].append(i)
        
    return combination(candidate_id, 0, 0, dict())