불량 사용자

불량 사용자
2019 카카오 개발자 겨울 인턴십 
1336명 완료
 
https://programmers.co.kr/learn/courses/30/lessons/64064

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

8개밖에 안되기 때문에 전수조사(brute force)로 해결 가능.

def solution(user_id, banned_id):
    from re import compile, match
    from itertools import permutations
    for index, banned in enumerate(banned_id):
        banned_id[index] = compile(f"{banned.replace('*', '.')}$")
    passed = set()
    for candidate in permutations(user_id, len(banned_id)):
        for index, each in enumerate(candidate):
            if not banned_id[index].match(each):
                break
        else:
            passed.add(tuple(sorted(candidate)))
    return len(passed)

테스트 1 〉	통과 (0.10ms, 10.8MB)
테스트 2 〉	통과 (0.63ms, 10.7MB)
테스트 3 〉	통과 (0.29ms, 10.6MB)
테스트 4 〉	통과 (0.24ms, 10.7MB)
테스트 5 〉	통과 (125.25ms, 10.6MB)
테스트 6 〉	통과 (15.68ms, 10.7MB)
테스트 7 〉	통과 (1.02ms, 10.8MB)
테스트 8 〉	통과 (0.71ms, 10.7MB)
테스트 9 〉	통과 (1.18ms, 10.7MB)
테스트 10 〉	통과 (20.21ms, 10.7MB)
테스트 11 〉	통과 (1.66ms, 10.6MB)

조합으로 해결하려고 노오력했으나..  
pr*do, pr**do 가 있을 때 등등에서 머리가 복잡해짐..
전수 조사 한 번 돌렸더니.. 머리가 맑아짐...

한 줄로..

from itertools import permutations
from re import compile


def solution(user_id, banned_id):
    return len(set(tuple(sorted(candidate)) for candidate in permutations(user_id, len(banned_id)) if
                   len(banned_id) == len(
                       [True for index, each in enumerate(candidate) if
                        [compile(f"{banned.replace('*', '.')}$") for banned in banned_id][index].match(each)])))

테스트 1 〉	통과 (0.10ms, 10.6MB)
테스트 2 〉	통과 (13.62ms, 10.7MB)
테스트 3 〉	통과 (1.71ms, 10.8MB)
테스트 4 〉	통과 (1.07ms, 10.6MB)
테스트 5 〉	통과 (1801.67ms, 10.8MB)
테스트 6 〉	통과 (522.44ms, 10.6MB)
테스트 7 〉	통과 (20.48ms, 10.6MB)
테스트 8 〉	통과 (10.44ms, 10.8MB)
테스트 9 〉	통과 (20.49ms, 10.6MB)
테스트 10 〉	통과 (1762.69ms, 10.7MB)
테스트 11 〉	통과 (46.99ms, 10.7MB)

두 줄로..

from itertools import permutations
from re import compile


def solution(user_id, banned_id):
    compiled = [compile(f"{banned.replace('*', '.')}$") for banned in banned_id]
    return len(set(tuple(sorted(candidate)) for candidate in permutations(user_id, len(banned_id)) if
                   len(banned_id) == len(
                       [True for index, each in enumerate(candidate) if
                        compiled[index].match(each)])))

테스트 1 〉	통과 (0.09ms, 10.7MB)
테스트 2 〉	통과 (1.49ms, 10.7MB)
테스트 3 〉	통과 (0.42ms, 10.6MB)
테스트 4 〉	통과 (0.33ms, 10.7MB)
테스트 5 〉	통과 (136.71ms, 10.6MB)
테스트 6 〉	통과 (43.07ms, 10.7MB)
테스트 7 〉	통과 (2.64ms, 10.7MB)
테스트 8 〉	통과 (1.46ms, 10.7MB)
테스트 9 〉	통과 (2.70ms, 10.7MB)
테스트 10 〉	통과 (97.33ms, 10.8MB)
테스트 11 〉	통과 (4.76ms, 10.7MB)