불량 사용자 (Level 3)

문제

 

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

프로그래머스

 

내 풀이

 

user_id와 banned_id의 배열 크기가 작아서 O(n^2)으로 풀어야겠다고 생각했다.

 

user와 banned를 비교한 후에 user가 banned와 길이가 같고 '*'을 제외한 나머지 문자들이 같으면 딕셔너리 dic에 user를 집어넣었다. 이렇게 함으로써 banned가 될 수 있는 user를 모았다.

이때 딕셔너리의 key는 인덱스로 하였는데, 그 이유는 처음부터 주어진 banned_id에 중복이 있을 수 있기 때문이다. 예제 3을 보면 바로 이해가 된다.

 

그리고 dfs (백트래킹)를 사용하여 모든 조합을 구하였다. 중복을 제거하기 위해 set을 사용하였다. 

final을 list로 선언하고 마지막에 set으로 형 변환을 하면 시간 초과가 난다. 그래서 final을 처음부터 set으로 선언해야 한다.

 

def solution(user_id, banned_id):
    dic = {i:[] for i in range(len(banned_id))}
    
    for user in user_id:
        for idx, banned in enumerate(banned_id):
            if len(user) == len(banned):
                flag = True
                for a, b in zip(user, banned):                    
                    if a == b: continue
                    else:
                        if a == '*' or b == '*': continue
                        else: flag = False
                if flag: dic[idx].append(user)
    final = set()
    check = [False]*len(banned_id)
    def dfs(idx, arr):
        if idx == len(banned_id):
            if len(set(arr)) == len(banned_id):
                final.add(tuple(sorted(arr[:])))
            return
        if not check[idx]:
            check[idx] = True
            for name in dic[idx]:
                arr.append(name)
                dfs(idx+1, arr)
                arr.pop()
            check[idx] = False
    
    dfs(0, [])
    return len(final)

 

총평

다른 레벨3보다는 괜찮았다.