[프로그래머스] 불량 사용자 (2019 카카오 겨울 인턴십)

프로그래머스 불량 사용자 문제 보기

문제풀이

1.banned_id마다 가능한 user_id를 찾아서 matchedList를 만든다.

[[1,2],[3,4],[3,4,5]] 
#이런식으로 각 banned_id가 될 수 있는 user_id의 idx로 matchedList를 만든다.

2.matchedList의 요소 갯수가 n일때, depth n으로 탐색하는 dfs로 조합을 만든다.
이때, 미리 matchedList를 정렬해놓고 + 조합을 set에 저장하면 중복을 없앨 수 있다.

3.set의 요소 갯수가 답이다.

정규식 사용

banned_id마다 가능한 user_id를 찾을때 정규식으로 찾았다. (dfs로 그냥 찾아도 될듯하다.)

# "fr*do" 같은 경우 아래와 같이 pattern을 만들어서 정규식을 사용한다.
re.match("fr.do$",uid) != None

Code

import re
answerSet = set()
matchedList =[]

def solution(user_id, banned_id):
    global answerSet
    global matchedList

    for bid in banned_id:
        matched = []
        p = ""
        for c in bid:
            if c=="*": p+="."
            else: p+=c
        p+="$"
        for uid in user_id:
            if re.match(p,uid) != None:
                matched.append(user_id.index(uid))
        matchedList.append(matched[:])

    dfs(0,len(banned_id),list())
    return len(answerSet)

def dfs(now,end,selected):
    global answerSet
    global matchedList

    if now == end:
        if len(set(selected))==len(selected):
            answerSet.add(tuple(sorted(selected)))
        return

    for e in matchedList[now]:
        selected.append(e)
        dfs(now+1,end,selected)
        selected.pop()