2019 카카오 개발자 겨울 인턴십 풀이

Level 1 - 크레인 인형뽑기 게임 풀이
Level 2 - 튜플 풀이
Level 3 - 불량 사용자 풀이
Level 4 - 호텔 방 배정 풀이
Level 3 - 징검다리 건너기 풀이

프로그래머스 - 불량 사용자 링크
(2022.11.01 기준 Level 3)

문제

알파벳 소문자와 숫자로 이루어진 이벤트 응모자 아이디 목록이 있고, 아이디 일부를 '*'로 가린 불량 사용자 아이디 목록이 있다. 이 때, 당첨에서 제외될 제재 아이디 목록의 경우의 수 출력

알고리즘

Top-down 느낌의 재귀함수를 이용하는 DFS를 사용해야 한다. 큰 틀은 비트마스킹을 이용하는 외판원 순회랑 비슷한?
이유는 풀이에서 후술.

풀이

두번째 TC를 살펴보자.

가능한 것끼리 이으면 이 모양이 된다.
만약, 첫번째 '*rodo'가 'frodo'랑 이으면, 두번째 '*rodo'는 'crodo'랑만 이어질 수 있다.
첫번째 '*rodo'가 'crodo'랑 이으면, 두번째 '*rodo'는 'frodo'랑만 이어진다.
결국 어떻게 잇든 'frodo'와 'crodo' 하나의 경우의 수만 나온다.
그래서 '******'가 'abc123'과 'frodoc' 두 개와 이어질 수 있으므로 답은 2가 되는 것이다.

결국 무슨 말이냐면, 불량 사용자랑 한번 매칭된 사용자 아이디는 두 번 매칭될 수 없으므로
재귀함수를 이용하여 DFS를 시작 및 매칭된 사용자 아이디는 비트마스킹을 이용하여 체크하고, 모든 불량 사용자가 사용자 아이디와 매칭이 됐으면 체크한 비트를 결과에 넣고, 마지막엔 중복된 결과를 set을 이용하여 제거한 뒤 개수를 출력하면 된다.

두번째 예제는 결과에 [13, 21, 13, 21]이 담겨진다.

1 -> 3 -> 4 (01101, 13)
1 -> 3 -> 5 (10101, 21)
3 -> 1 -> 4 (01101, 13)
3 -> 1 -> 5 (10101, 21)

위와 같이 담겨지는 순서를 생각해보면 이해가 될 것이다.
나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리해야 하기 때문에, 중복을 제거하는 것이다.

코드

def solution(user_id, banned_id):

    # 응모자 아이디와 불량 아이디가 매칭이 가능한지 확인하는 함수
    def check(user, banned):
        if len(user) == len(banned): # 길이가 같아야 한다.
            for i in range(len(user)):
                if banned[i] != '*' and user[i] != banned[i]:
                    break
            else:
                return True
        return False

    # DFS
    # 첫번째 불량 아이디부터 매칭을 시작
    def dfs(i, v):
        if i == b: # 불량 아이디 수만큼 매칭을 했으면
            result.append(v) # 현재 매칭된 응모자 아이디를 담은 비트를 result에 저장
            return
        for j in range(u):
            # 매칭되지 않은 응모자 아이디이며 현재 불량 아이디와 매칭이 가능한지 확인
            if not v & (1 << j) and check(user_id[j], banned_id[i]):
                dfs(i + 1, v | (1 << j))

    u = len(user_id)
    b = len(banned_id)

    result = []
    dfs(0, 0)

    # 중복을 제거하여 개수 반환
    return len(set(result))

여담

처음엔 이분 매칭인 줄 알고 풀다가 문제점을 깨닫고 다시 알맞게 풀었다.
태그가 걸리지 않아서 어떻게 풀어내는지 알아내는게 더 어려웠던 문제.