[2019 카카오 인턴십] 불량 사용자 (feat. PYTHON)

def nCr(temp, number, matched_group):
    global result
    if len(temp) == len(matched_group):
        temp = set(temp)
        if temp not in result:
            result.append(temp)
        return
    else:
        for j in range(len(matched_group[number])):
            if matched_group[number][j] not in temp:
                temp.append(matched_group[number][j])
                nCr(temp, number+1, matched_group)
                temp.pop()

result = []
def solution(user_id, banned_id):
    global result
    matched_group = []
    for ban in banned_id:
        matched_user = []
        for user in user_id:
            if len(ban) != len(user):
                continue
            else:
                save_flag = True
                for i in range(len(ban)):
                    if user[i] != ban[i] and ban[i] != '*': 
                        save_flag = False
                        break
                if (save_flag): 
                    matched_user.append(user)
        matched_group.append(matched_user)

    nCr([], 0, matched_group)
    return len(result)

풀이

1. 불량유저로 선택될 수 있는 모든 유저를 검사하여 각각 리스트그룹으로 저장한다.

2. nCr(dfs)로 가능한 모든 경우의 수를 계산한다.

 

내가 시험문제를 풀었을 때는 dfs를 제대로 구성하지 못해서 예제3개 중 2개만 맞아서 다른사람의 코드를 참고하였다.
# dfs 공부 다시해야함

 

문제해설 https://tech.kakao.com/2020/04/01/2019-internship-test/

[문제3 풀러 가기]