[프로그래머스] 64064. 불량 사용자

2019 카카오 개발자 겨울 인턴십 - 64064. 불량 사용자

Python 풀이

 

풀이

우선

• user_id 배열의 크기는 1 이상 8 이하입니다.
• banned_id 배열의 크기는 1 이상 user_id 배열의 크기 이하입니다.

의 조건이 존재하기 때문에, 효율성을 크게 따질 필요는 없어 보임.

 

isSame() => banned ID에 user ID가 들어갈 수 있는 지 확인하는 함수.

하나 만들어 놓고,

빈 dictionary(able) 생성해서, banned_id 의 index 순으로 대입 가능한 user_id 의 배열을 집어넣어 놓음.

 

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

의 예시에서,

able = {0: ['frodo', 'fradi'], 1: ['frodo', 'crodo'], 2: ['abc123', 'frodoc'], 3: ['abc123', 'frodoc']}

과 같은 dictionary가 만들어지게 됨.

 

그리고, DFS로 모든 경우의 수를 탐색.

위와 같은 예시의 경우, 아래와 같이 6가지 경우의 수가 나오게 됨.

[['frodo', 'crodo', 'abc123', 'frodoc'], 
 ['frodo', 'crodo', 'frodoc', 'abc123'], 
 ['fradi', 'frodo', 'abc123', 'frodoc'], 
 ['fradi', 'frodo', 'frodoc', 'abc123'], 
 ['fradi', 'crodo', 'abc123', 'frodoc'], 
 ['fradi', 'crodo', 'frodoc', 'abc123']]

이것을 다시 set으로 변환하면 똑같은 경우의 수는 사라짐.

그러나 set은 mutable하여 set의 원소가 될 수 없으므로,

각 set {'', '', '', ''}을 list로 변환한 후,

각 list을 정렬(set->list이므로 순서가 뒤죽박죽되어 같은지 검사하려면 정렬 필요)하여,

다시 각 list를 tuple로 변환하여

전체를 set으로 변환. 아래와 같이.

set(map(tuple, map(sorted, map(list, AllList))))

이후 원소의 숫자가 정답.

 

전체 Code

def solution(user_id, banned_id):
    def isSame(user, ban):
        if len(user) != len(ban):
            return False

        for i in range(len(ban)):
            if ban[i] == '*':
                continue
            else:
                if ban[i] != user[i]:
                    return False

        return True


    able = {i: [] for i in range(len(banned_id))}

    for i, ban in enumerate(banned_id):
        for user in user_id:
            if isSame(user, ban):
                able[i].append(user)

    AllList = []


    def dfs(a, i):
        if i == len(banned_id):
            temp = a[:]
            AllList.append(temp)
            return

        for user in able[i]:
            b = a[:]
            # 중복 피하기 (시간초과)
            if user in b:
                continue
            b.append(user)
            dfs(b, i+1)
            del b[0]


    dfs([], 0)

    return len(set(map(tuple, map(sorted, map(list, AllList)))))