[프로그래머스/파이썬] 불량 사용자(64064) 풀이

---

• 프로그래머스 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 프로그래머스 코딩테스트 연습
• 문제 링크: 불량 사용자(64064)
• 문제풀이 코드 GitHub 링크
• 풀이 언어: Python 3

풀이

문제

와일드카드(*)가 포함된 banned_id 패턴들에 대해 user_id를 중복 없이 매칭시키는 모든 경우의 수를 구하는 문제입니다.

같은 사용자 조합이라면 순서가 달라도 1개로 취급합니다.

코드

def solution(user_id, banned_id):
    answer = []
    banned_id.sort()
    dfs(banned_id, 0, set(user_id), tuple(), answer)
    
    return len(set(answer))

def dfs(banned_id, index, uid_set, comb, answer):
    if index >= len(banned_id):
        answer.append(tuple(sorted(comb)))
        return
    
    for uid in uid_set:
        if len(uid) != len(banned_id[index]): continue
        banned = True
        for i in range(len(uid)):
            if banned_id[index][i] != uid[i] and banned_id[index][i] != '*':
                banned = False
                break
        if banned: dfs(banned_id, index+1, uid_set-set([uid]), comb+tuple([uid]), answer)
    

print(solution(["frodo", "fradi", "crodo", "abc123", "frodoc"], ["fr*d*", "abc1**"]))

설명

DFS로 banned 패턴을 하나씩 처리합니다.

• 현재 패턴과 길이/문자 조건이 맞는 user를 고릅니다.
• 고른 user는 다음 단계에서 제외합니다.
• 끝까지 매칭되면 조합을 정렬 튜플로 저장합니다.

마지막에 set(answer) 크기를 반환하면 순서만 다른 중복 조합이 제거된 경우의 수를 얻을 수 있습니다.

---

• 프로그래머스 문제풀이 전체 목록 보기

---