[프로그래머스] 파이썬 _ 불량 사용자 (2018 KAKAO WINTER INTERN)

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

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

 

문제유형 : 잘모르겠다.. 나는 DFS로 풀긴햇답

 

문제풀이 :

 

DFS 과정 

DFS를 하면서 depth를 저장하면서 진행한다.

depth가 끝까지 도달했다면 현재경로까지 추가된 노드들을 copy해서 전역변수에 저장하고 리턴한다.

dfs를 재귀호출하는 다음부분에 현재경로에서 현재노드(마지막노드)를 제거한다. 그다음 dfs를 호출하면 이전까지의 경로는 그대로 있고 마지막 노드들만 싹싹(?) 교체됨

 

DFS의 결과로 나온 모든 경로를 담고있는 2차원 배열에서 각각을 집합으로 바꾼다. ( 중복노드 제거를 위해)

이때 중복이 제거된 후에도 전체 길이가 banned_id와 같다면 하나의 경우를 찾은것이므로 저장해놓는다.

이때 (a,b,c) (b,c,a)를 같은경우로 쳐줘야하므로 한번 정렬한후에 집합에 추가함으로서 최종적으로 모든 중복경우를 제거할 수 있다.

 

match함수

별표가 포함된 단어와 대상이될 단어를 매개변수로 받아 둘이 매칭되는지 확인하는 함수

이때 길이가 다르다면 더이상 확인할필요없이 바로 False를 리턴한다.

*이면 넘어가고 *가 아닐때 서로 문자를 비교하여 다르면 False를 리턴한다.

중간에 조기리턴 되지않고 모두 코드가 완료되면 서로 같다는 뜻이므로 True를 리턴한다.

 

 

정답코드 :

from collections import Counter
from itertools import combinations

temp = []
# 전체사용자 - user_id, 불량사용자목록 - banned_id
# 가능한 경우의수 (전체에서 해당되는 사용자들을 모두 찾고 조합갯수?)
def solution(user_id, banned_id):
    answer = 0
    one_list = []
    if len(Counter(banned_id).keys())==1:
        for j in user_id:
            if match(j, banned_id[0]):
                one_list.append(j)

        return len(list(combinations(one_list,len(banned_id))))




    ban_len = len(banned_id)
    match_list = [[] for _ in range(ban_len)]

    for idx, i in enumerate(banned_id):
        for j in user_id:
            if match(j, i):
                match_list[idx].append(j)
    # print(match_list)

    for i in match_list[0]:
        curr = []
        dfs(i, 0, match_list[1:], curr)
    result = set()

    for i in temp:
        i = set(i)
        if len(i) != ban_len:
            continue
        result.add(tuple(sorted(i)))

    return len(result)


# ['frodo', 'crodo'], ['abc123', 'frodoc']]
def dfs(start, depth, graph, curr):
    curr.append(start)

    if depth == len(graph):
        temp.append(curr.copy()) ## 또오오오오오오오오 copy안하면 레퍼런스가 들어가므로 꼭 기억 
        return

    for i in graph[depth]:
        dfs(i, depth + 1, graph, curr)
        curr.remove(i)


def match(target, banid):

    if len(target) != len(banid):
        return False
    for idx, i in enumerate(banid):
        if i == '*':
            continue
        else:
            if target[idx] != i:
                return False
    return True