불량 사용자

• Difficulty: Level 3
• Type: Hash
• link

Problem

공식 문제풀이

Solution

• 문제 풀이 인용: "응모자 아이디 목록의 길이가 N, 불량 사용자 아이디 목록의 길이가 K 일 때, 응모자 아이디 N개 중 K개를 선택하는 모든 방법을 시도해 봅니다. 선택된 아이디 목록이 불량 사용자 목록으로 매핑될 수 있다면 카운트를 하나 증가시킵니다. 최종적으로 매핑에 성공한 횟수를 반환하면 됩니다."

import itertools
import re

def solution(user_id, banned_id):
    banned_id = [re.sub("[*]",".",b) for b in banned_id]
    # 'matches' provide a list of sets which could be hashed by each banned id
    # e.g: [{'crodo', 'frodo'}, {'crodo', 'frodo'}, {'abc123', 'frodoc'}]
    matches = []
    # 'total_matches' is a set of all the words matched by the banned_id
    # e.g: {'frodoc', 'abc123', 'frodo', 'crodo'}
    total_matches = set([])
    # 'pool' is a list of combination which could all be hashed to the match
    # [{'frodoc', 'frodo', 'crodo'}, {'abc123', 'frodo', 'crodo'}]
    pool = []

    for b in banned_id:
        count = 0
        match_set = set([])
        for w in user_id:
            # Find exact match
            m = re.match(f"^{b}$",w)
            if m and m.string not in match_set:
                match_set.add(m.string)
                total_matches.add(m.string)
        matches.append(match_set)


    perm_list = list(map(list,itertools.permutations(total_matches,len(banned_id))))
    for p in perm_list:
        # Increment count only if all the words could be hashed to the match
        if all([p[i] in matches[i] for i in range(len(p))]) and set(p) not in pool:
            pool.append(set(p))

    return len(pool)