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

우선 정규표현식을 이용하여 불량 사용자 아이디 마다 매칭되는 유저들 리스트를 갖는 banned_id_matches 리스트를 만든다.
예를 들면, 입출력 첫 번째 예에서는 banned_id_matches [["frodo", "fradi"], ["abc123"]] 가 된다.

이제 banned_id_matches 요소마다 유저의 아이디를 중복이 되지 않게 하나씩 선택하면 된다.
유저 아이디 개수가 적었기 때문에 완전 탐색을 했고 백트래킹 방식으로 구현하였다.

백트래킹을 하기 위한 search 함수를 만들고 banned_id_matches은 전역으로 선언해놓았기 때문에 인자 값으로는 (이미 선택한 유저 아이디 set, banned_id_matches 인덱스)만 넘겨준다.

인덱스가 불량 사용자 아이디 개수가 되면(banned_id_matches의 모든 인덱스를 살펴봄) 선택한 유저 아이디 set을 answer에 같은 set이 존재하지 않는다면 answer에 넣어준다. answer에 같은 set이 존재하지 않을 때 넣어주는 이유는 set에 넣는 순서가 "frodo", "fradi" 순서 일 때와 "fradi", "frodo" 일 때가 존재할 수도 있는데 이 때 중복으로 answer에 넣으면 안되기 때문이다.

import re
from copy import deepcopy

answer = []
banned_id_matches = []


def solution(user_ids, banned_ids):
    global answer, banned_id_matches

    set_banned_id_matches(user_ids, banned_ids)
    search(set(), 0)

    return len(answer)


def set_banned_id_matches(user_ids, banned_ids):
    for i in range(len(banned_ids)):
        p = re.compile("^" + banned_ids[i].replace("*", ".") + "$")
        banned_id_matches.append({user for user in user_ids if p.match(user)})


def search(visited, idx):
    if idx == len(banned_id_matches):
        if visited not in answer:
            answer.append(deepcopy(visited))
        return

    for user in banned_id_matches[idx]:
        if user in visited:
            continue

        visited.add(user)
        search(visited, idx + 1)
        visited.remove(user)