[프로그래머스/2019 카카오 개발자 겨울 인턴십/python] 불량사용자

로직

 

불량 사용자 후보군 추출

먼저 불량 사용자 리스트를 통해서 제재 대상이 될 후보군들을 추출한다( 추출 시에 정규 표현식을 사용했다)

 

만약에 아래와 같은 예시가 있다면 

user_id = ["frodo", "fradi", "crodo", "abc123", "frodoc"]
banned_id = ["*rodo", "*rodo", "******"]

 

 

각 불량 사용자에 대한 후보군들은 아래와 같다.

*rodo ['frodo', 'crodo']
*rodo ['frodo', 'crodo'] 
****** ['abc123', 'frodoc']

DFS 탐색

이후 dfs로 제재 아이디 목록을 찾아낸다.

 

만약 leaf까지 탐색했다면
완성된 제재 리스트가 현재 이미 만들어진 제재 리스트에 없다면( stack not in candidates ) 후보군으로 넣어준다.

제재 리스트 후보군들은 모두 set()으로 저장되기 때문에 중복을 허용하지 않는다. ([a, b]와 [b, a]가 따로 카운트될 위험이 없다)

 

코드

import re
import copy

# 최단거리 문제는 보통 BFS가 유리하다.
# 단 path를 다 기억해야하는 경우에는 DFS 방식을 사용하는 것이 좋다
# https://devuna.tistory.com/32 '적합'

def solution(user_id, banned_id):
    answer = [[] for i in range(len(banned_id))]

    # 각 banned_id와 매칭되는 id들을 저장
    for idx, ban_id in enumerate(banned_id):
        pattern = ban_id.replace('*', '.')
        for user in user_id:
            matched = re.match(pattern, user)
            if matched and len(matched.group()) == len(user):
                answer[idx].append(user)

    # 제재 아이디 목록 후보군 저장할 리스트
    global candidates
    candidates = []

    # dfs 탐색
    counter = dfs(answer)

    return counter

def dfs(answer, level = 0, stack = []):
    counter = 0

    # break point
    if level >= len(answer):
        set_stack = set(stack)          # set => 중복제거를 위해서 set([a, b]) == set([b, a])
        if set_stack not in candidates: # 이미 만들어놓은 제재 아이디 목록이 아니라면 카운트
            candidates.append(set_stack)
            return 1
        else: return 0

    # 현재 level
    for user_id in answer[level]:
        # 만약에 현재 탐색하는 user_id가 이미 현재 만들고 있는 아이디 목록에 있으면 의미 없기 때문에 넘어간다.
        if user_id in stack: continue
        stack.append(user_id)
        # 한 레벨 더 내려가서 다음 id 선택
        counter += dfs(answer, level + 1, copy.deepcopy(stack))
        # backtracking
        stack.pop()
    return counter