[プログラマー]不良ユーザー

出典:プログラマーコードテスト練習、[プログラマー]不良ユーザー

に答える

1.まずビットマスクを使用し、応募者IDにおいて不良ユーザ数によるフィルタリングを繰り返してはならない.
2.優先検索を深く行い、選択されたユーザと不良ユーザが一致しているかを確認する.このときはすべて探索せず,Trueになるとすぐに返却され,タイムアウトしない.
3.一致しているか確認する方法を作成します.2つのIDの長さが異なる場合、Falseが返される.

コード#コード#

def match(uid, bid):
    if len(uid) != len(bid): return False
    for v1, v2 in zip(uid, bid):
        if v2 == '*': continue
        if v1 != v2: return False
    return True

# 두 리스트 크기 같아야 됨
def match_list(uid_list, bid_list):
    if not uid_list and not bid_list:
        return True
    for i in range(len(uid_list)):
        for j in range(len(bid_list)):
            if match(uid_list[i], bid_list[j]):
                if match_list(uid_list[:i] + uid_list[i+1:], bid_list[:j] + bid_list[j+1:]):
                    return True
    return False

def solution(user_id, banned_id):
    answer = 0
    N = len(user_id)
    M = len(banned_id)
    for i in range(1, 1 << N):
        if bin(i)[2:].count('1') != M: continue
        uid_list = []
        for j in range(N):
            if i & (1 << j):
                uid_list.append(user_id[j])
        if match_list(uid_list, banned_id):
            answer += 1
    
    return answer

に感銘を与える

文字列の組み合わせの問題が発生した場合は、正規表現で解決する考えを放棄します.繰り返し文で一致する方法を作成するのは、より簡単な方法かもしれません.