불량 사용자

🤡불량 사용자 (Lv.3)

🤑풀이

import itertools

def make_hash(user_id, bannded_id) :
    lst = []
    for bid in bannded_id :
        bid_lst = []
        for uid in user_id :
            match = True
            if len(bid) == len(uid) :
                for i in range(len(bid)) :
                    if bid[i] == '*' :
                        continue
                    elif bid[i] != uid[i] :
                        match = False
                        break
                if match :
                    bid_lst.append(uid)
        lst.append(bid_lst)
    return lst


def solution(user_id, banned_id) :
    answer_lst = []
    info_lst = make_hash(user_id, banned_id)
    
    for lst in itertools.product(*info_lst) :
        set_combi = set(lst)
        if len(set_combi) < len(banned_id) :
            continue
        else :
            if len(answer_lst) == 0 :
                answer_lst.append(set_combi)
            else :
                exist = False
                for already in answer_lst :
                    if already == set_combi :
                        exist = True
                        break
                if not exist :
                    answer_lst.append(set_combi)
    return len(answer_lst)

👩‍🏫 아이디어

• banned_id가 될 수 있는 user_id의 목록을 담은 list 생성.
  • banned_id가 중복될 수 있으므로 hash table로 생성하지 않고 list로 생성
• itertools의 product를 사용하여 list of list의 조합 생성.
  • 최대 2^24의 연산이 요구되는 좋지 않은 단순한 풀이.
  • user_id list의 길이가 조금만 더 길어도 시간초과가 발생할 것 같다.
  • 조금 더 효율적인 방법이 없을까 고민해보자.
• 각 조합된 id list에 대해서 새로 추가할지 여부를 조건에 따라서 결정.