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

문제

• 응모자 아이디와 불량 사용자 아이디 리스트가 있을 때, 불량 사용자에 매핑되는 응모자 아이디의 조합 개수 리턴하기
• 불량 사용자 아이디에 * 이 포함되면 어떤 문자든 매핑이 가능하다는 의미다.
• 1 <= 응모자 아이디 개수 <= 8

 

풀이

1. 각 불량 아이디별로 매칭이 가능한 사용자 아이디 목록 뽑아내기
   • re.match : 문자열 선두가 패턴에 매치되는지 판단한다.
     • 인식타입 중 . 은 모든 문자를 의미하기 때문에 * 를 변환해 사용하도록 한다.
     • 문자열의 길이 또한 일치해야 하므로 문자열 끝을 의미하는 $ 를 추가한다.
2. 각 불량 아이디별 매칭된 사용자 아이디 목록의 순서 조합
3. 매칭된 사용자 아이디 개수가 불량 아이디 개수와 일치하는지 확인
   • 불량 아이디가 3개 이고 각각 매칭되는 사용자 아이디가 [0, 2] [0, 1] [2, 3] 일 때 product 로 만들 수 있는 모든 조합의 수는 다음과 같다. 
     [0, 0, 2] [0, 0, 3] [0, 1, 2] [0, 1, 3] ..... 
     위 경우의 수에서 [0, 0, 2] 또는 [0, 0, 3] 는 사실상 2개의 사용자 아이디가 매칭되므로 불량 아이디별 사용자 아이디 매칭 조합이 될 수 없으므로 제외해야 한다.

 

import re
from itertools import product

def solution(user_id, banned_id):
    # 1) 각 불량 아이디별로 매칭이 가능한 사용자 아이디 목록 뽑아내기
    matched_id = (
        [i for i, id in enumerate(user_id) if re.match(f"^{p.replace('*', '.')}$", id)]
        for p in banned_id
    )

    # 2) 각 불량 아이디별 매칭된 사용자 아이디 목록의 순서 조합
    # selected_id = [set(id) for id in product(*matched_id)]  # <- 시간초과
    selected_id = (set(id) for id in product(*matched_id))    # <- 통과

    # 3) 매칭된 사용자 아이디 개수가 불량 아이디 개수와 일치하는지 확인
    selected_id = set(tuple(id) for id in selected_id if len(id) == len(banned_id))

    return len(selected_id)

 

References

• 프로그래머스 Lv3 불량 사용자