[2019 카카오 개발자 겨울 인턴십] 불량 사용자

네이버 코테에 대비하기 위해 오늘도 문제를 풀어보았습니다.
프로그래머스 레벨 3 위주로 푸는데 오랜만에 풀어서 그런지 잘 풀리지 않아 살짝 불안합니다..

이번에 푼 문제는 불량 사용자입니다. 요즘 코딩테스트에 문자열 문제가 빠지지 않는 것 같아 일부러 문자열 문제를 골랐습니다. 마지막에 막혀서 결국 다른 분의 코드를 참고한 문제입니다.

문제를 간단히 설명하자면, 전체 user_id 중에서 불량 사용자의 id를 골라내는 문제입니다. 불량 사용자의 id는 일부 글자가 * 처리돼있는 형태로 주어지는데, 이런 경우 *의 자리에 아무 글자가 들어간 id라도 불량 사용자로 간주할 수 있습니다.

예를 들어,

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

인 경우에, 첫 불량 사용자 아이디인 *rodo는 frodo, crodo 모두 해당될 수 있고, fr*d*의 경우에는 frodo, fradi 두 사용자가 해당될 수 있으며 ,마지막 불량사용자는 abc123 혼자 해당되는 아이디입니다.

이렇게 주어진 사용자 id와 불량 사용자 id를 토대로 불량 사용자를 고르는 경우의 수를 묻는 문제입니다.

문제 접근은 우선, 각 불량 사용자 id를 기준으로 해당 id에서 불량 사용자로 고를 수 있는 user_id부터 조사하기로 했습니다.

> def solution(user_id, banned_id):
    # 불량 사용자 후보 배열을 저장할 배열
    candidates = []

    # 불량 사용자 아이디를 순회하며 후보 배열 작성
    for b_id in banned_id:
    	# 한 불량 사용자 아이디 당 후보를 저장할 배열 작성
        temp = []
        for id in user_id:
            
            if len(id) == len(b_id):
                for i in range(len(id)):
                    if b_id[i] == '*' or b_id[i] == id[i]:
                        continue
                    else:
                        break
                else:
                    temp.append(id)
        if temp:
            candidates.append(temp)
            
    print(candidates)

입력값 〉 ["frodo", "fradi", "crodo", "abc123", "frodoc"],
["frd", "*rodo", "******", "******"]
출력 〉 [['frodo', 'fradi'], ['frodo', 'crodo'], ['abc123', 'frodoc'], ['abc123', 'frodoc']]

이렇게 뽑은 후보 배열들 중에서 이제 경우의 수를 세야 합니다.
제가 막힌 부분은 여깁니다. 출력값을 보면 frodo라는 사용자는 첫 후보에도 들어가고 두 번째 후보에도 포함되어 있습니다. 이렇기 때문에 중복 처리를 해서 계산해야 합니다.

처음에는 사실 Dictionary를 사용해서 각 banned_id를 key로 가지고 후보 배열을 value로 가진 다음 계산해보려 했는데 수학적으로 계산할 방법이 보이지 않았습니다.

이럴 땐 역시 완전 탐색이죠. 그 중에서도 DFS를 사용하면 됩니다.
각 후보 배열을 Node로 생각해서 한 Node씩 순회하며 중복된 user가 들어가지 않도록 하여 순회하면 됩니다.

DFS 과정은 우선 후보 배열에서 하나씩 pop하여 pop된 요소를 하나씩 꺼내면서 경로에 추가하고 다음 node로 보내기 위해 재귀를 사용하는 식으로 백트래킹을 했습니다. 이 때, 경로에 포함된 사용자는 다음 node로 보낼 때, user 목록에서 제외하여 중복 선택되지 않도록 처리했습니다.

코드는 다음과 같습니다.

def dfs(candidates, users, result, results):
    
    # 더 이상 순회할 노드가 없다 -> 최종 결과를 저장하는 results에 경로를 저장
    if not candidates:
        # 경로 간 중복을 제거하기 위해 경로를 정렬 후 set 자료형에 저장
        # 이 때, list는 set에 직접 넣을 수 없으므로 tuple로 변환한다
        results.add(tuple(sorted(result)))
        return 
        
    new_candidates = deepcopy(candidates)
    curr = new_candidates.pop()
    for user in curr:
        if user in users:

            new_result = deepcopy(result)
            new_result.append(user)
            new_users = deepcopy(users)
            new_users.remove(user)
            
            dfs(new_candidates, new_users, new_result, results)
    

candidates는 위에서 만든 후보 배열이고, users는 문제에서 주어진 user_id, 한 case의 result는 경로를 저장할 배열, results는 모든 case의 결과를 저장할 정답 set입니다.

이 때, 포인트는 경로 중에서도 중복된 경로가 존재하는데, 문제에서는 순서를 고려하지 않았으므로 경로들도 중복처리를 해줘야 합니다. 이 때, 경로들은 list로 저장되므로 단순히 set에 담아서 중복 처리가 되지 않습니다. 즉, set에 담기 전 정렬을 한 번 해주고 담아줍니다. 이 때, list는 unhashable하므로 tuple로 변환해야 한다고 합니다. (배울 point)

마지막으로 results의 길이를 return해주면 모든 경우의 수를 return하게 됩니다. 전체 코드는 다음과 같습니다.

from copy import deepcopy

def solution(user_id, banned_id):
    # 불량 사용자 후보 저장할 배열
    candidates = []

    # 불량 사용자 아이디를 순회하며 후보 배열 작성
    for b_id in banned_id:
        temp = []
        for id in user_id:
            
            if len(id) == len(b_id):
                for i in range(len(id)):
                    if b_id[i] == '*' or b_id[i] == id[i]:
                        continue
                    else:
                        break
                else:
                    temp.append(id)
        if temp:
            candidates.append(temp)
        
    # 경우의 수 조회를 DFS로 구현
    results = set()
    dfs(candidates, user_id, [], results)
    
    return len(results)

def dfs(candidates, users, result, results):
    
    # 더 이상 순회할 노드가 없다 -> 최종 결과를 저장하는 results에 경로를 저장
    if not candidates:
        # 경로 간 중복을 제거하기 위해 경로를 정렬 후 set 자료형에 저장
        # 이 때, list는 set에 직접 넣을 수 없으므로 tuple로 변환한다
        results.add(tuple(sorted(result)))
        return 
        
    new_candidates = deepcopy(candidates)
    curr = new_candidates.pop()
    for user in curr:
        if user in users:

            new_result = deepcopy(result)
            new_result.append(user)
            new_users = deepcopy(users)
            new_users.remove(user)
            
            dfs(new_candidates, new_users, new_result, results)
    

시간 복잡도 = O(N^2M) ? N = 사용자 id 개수 , M = 불량 사용자 id 개수

배울 점 : Set에는 list를 넣으면 unhashable type error가 발생한다