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

https://programmers.co.kr/learn/courses/30/lessons/64064

코딩테스트 연습 - 불량 사용자

쉬울 줄 알았는데 생각보다 오래 걸렸다..

 

처음 풀이는 ban 사용자 가지고 조합을 짜서 user_id를 만족하면 answer를 추가해주는 방식으로 코드를 짰다.

 

처음 풀이

import re
from collections import Counter
from itertools import product
def solution(user_id, banned_id):
    banned = {}
    answer = 0
    comb = [[] for _ in range(len(banned_id))]

    for i,ban in enumerate(banned_id):
        target = re.compile(ban.replace('*','.')+'$')
        for user in user_id:
            if target.match(user):
                comb[i].append(user)
    user_count = Counter(user_id)
    ban_product = set(sorted(list(product(*comb))))
    print(ban_product)
    for ban in ban_product:
        counted = Counter(ban)
        if len(counted-user_count)==0:
            banned[ban]=0
            answer+=1
    return answer

하나의 테스트 케이스에서 시간 초과가 났다.

두번 째 풀이

from itertools import permutations

def isMatch(user_set, banned_set):
    for i in range(len(user_set)):
        if len(user_set[i])!=len(banned_set[i]):
            return False
        for j in range(len(user_set[i])):
            if banned_set[i][j]=='*':
                continue
            if user_set[i][j]!=banned_set[i][j]:
                return False
    return True

def solution(user_id, banned_id):
    ans=[]
    for com_set in permutations(user_id, len(banned_id)):
        if isMatch(com_set, banned_id):
            com_set = set(com_set)
            if com_set not in ans:
                ans.append(com_set)
    return len(ans)