[프로그래머스 level3 불량 사용자] dictionary와 dfs 활용하기

해결해야하는 문제는 다음과 같았다.

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

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

 

 

 

이러한 아이디어를 바탕으로 작성한 코드는 다음과 같다.

answer = []
def dfs(ban_dict, ban_ids, idx, id_set):
    if len(ban_ids) == idx :
        if set(id_set) not in answer:
            answer.append(set(id_set))
        return

    now = ban_ids[idx]
    for i in range(len(ban_dict[ban_ids[idx]])) :
        if ban_dict[now][i] in id_set :
            continue
        id_set.append(ban_dict[now][i])
        dfs(ban_dict,ban_ids, idx+1, id_set)
        id_set.pop()


def solution(user_id, banned_id):
    banned_dict = {}

    for b in banned_id :
        banned_dict[b] = []

    for bi in banned_id :
        for ui in user_id :
            if len(bi) != len(ui):
                continue
            for idx in range(len(bi)) :
                if bi[idx] == '*':
                    continue
                if bi[idx] != ui[idx] :
                    break
            else :
                if ui not in banned_dict[bi]:
                    banned_dict[bi].append(ui)

    dfs(banned_dict,banned_id,0,[])

    return len(answer)

 

 

 

메모리가 굉장히 많은 경우, 순열을 통해 모든 경우의 수를 조합하고 답이 될 수 있는 쌍을 찾아내는 방식도 가능하다! 하지만 이는 메모리 제한이 있는 경우, 모든 순열 경우의 수를 따지기는 힘들기 때문에 메모리 측면에서는 효율적인 것 같지는 않다. 하지만 이 방식의 경우 코드가 짧고 가독성이 좋아서 가져와보았다.

from itertools import permutations
def check_id(combo_ids,banned_ids):
    for i in range(len(combo_ids)):
        if len(combo_ids[i]) != len(banned_ids[i]) :
            return False
        for j in range(len(combo_ids[i])):
            if banned_ids[i][j] == '*':
                continue
            if combo_ids[i][j] != banned_ids[i][j] :
                return False
    return True


def solution(user_id, banned_id):
    answer = []
    for ui in permutations(user_id,len(banned_id)):
        if check_id(ui,banned_id):
            if set(ui) not in answer :
                answer.append(set(ui))

    return len(answer)