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

문제설명

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

불량사용자 목록을 보고 응모자 아이디가 될 수 있는 경우의 수를 찾는 문제.

*가 임의의 한 문자를 의미하므로 이로 인해 경우의 수가 생성된다.

user_id의 길이 및 원소의 길이가 최대 8로 경우의 수가 매우 작은 문제이다.

접근방법

문자 비교는 kmp,보이어 무어도 있겠지만 구현이 좀 까다로워서 trie로 접근하였다.

trie

1. trie에 user_id넣기

2. banned_id하나하나에 대하여

   2-1. 해당 banned_id가 가질 수 있는 user_id 경우 찾기

   ​ 2-1-1. 이때 banned_id의 각 한글자에 대해 탐색하여 *를 만나면 모든 child노드 탐색하여 경우에 추가.

   ​ 2-1-2. 한글자가 노드에 없다면 불가능한 경우이므로 이는 경우의 수에 추가하지 않는다.

   2-2. 찾았다면 user_id를 삭제하고 2번으로 돌아간다.

3. banned_id를 모두 탐색했다면 가능한 user_id 또는 삭제하고 남은 user_id를 선택한 케이스에 넣기

   • 이때 user_id를 정렬해주어야 한다. (중복선택되는 경우가 존재하므로 123선택 213선택)

구현

class NODE:
    def __init__(self):
        self.children = {}
        self.endOfWord = False

def inserValue(root,id):
    curNode = root
    for char in id:
        if char not in curNode.children:
            curNode.children[char] = NODE()
        curNode = curNode.children[char]
    curNode.endOfWord = True

def FindPossibleValues(bId, rootNode):
    initChar = bId[0]
    curStack = []  # 원소 노드,여태까지 문자
    if initChar == "*":
        for key in rootNode.children:
            curStack.append((key, rootNode.children[key]))
    else:
        curStack.append((initChar, rootNode.children[initChar]))

    for char in bId[1:]:
        nxtStack = []
        if char == '*':
            while curStack:
                subString, curNode = curStack.pop()
                for key in curNode.children:
                    nxtStack.append((subString + key, curNode.children[key]))
        else:
            while curStack:
                subString, curNode = curStack.pop()
                if char not in curNode.children:
                    continue
                nxtStack.append((subString + char, curNode.children[char]))

        curStack = nxtStack

    possibleValues = []
    for uid,node in curStack:
        possibleValues.append(uid)
    return possibleValues

def solution(user_id, banned_id):
    answer = 0
    rootNode = NODE()

    for uId in user_id:
        inserValue(rootNode,uId)

    banned_id = banned_id
    user_id = set(user_id)

    rst = set()
    def CountAnswer(user_id,banned_id,rootNode):
        nonlocal answer
        if not banned_id:
            user_id = list(user_id)
            user_id.sort()
            rst.add(tuple(user_id))
            return

        bId = banned_id.pop()
        possibleValues = FindPossibleValues(bId,rootNode)

        for possibleUId in possibleValues:
            if possibleUId not in user_id:
                continue
            CountAnswer(user_id-{possibleUId},banned_id.copy(),rootNode)

    CountAnswer(user_id,banned_id,rootNode)

    answer = len(rst)
    return answer

위처럼 보듯 좀 복잡하다. banned_id 리스트를 기준으로, 그 안에 banned_id 원소를 기준으로 또 탐색과정을 거쳐야해서 코드가 복잡해졌다. 그래서 이번엔 구현할 때 시간을 30분정도 소요했다.

그리고 trie를 클래스로 선언하지 않은 이유는 논리적으로 class내 insert와 search가 같이 있어야 의미가 맞겠으나, banned_id탐색 아래에 search를 두자니 구분이 불명확해지는 느낌이 들었다. trie의 독립된 객체가 아니고 종속관계가 심해진 것 같아서 위와같이 두었다.