[Programmers] P64064 불량 사용자

[Programmers] P64064 불량 사용자

Question

Language: Python

유저 id n개 중에서 banned_id로 매칭되는 조합의 개수를 찾아야한다.

즉, banned_id를 이용해서 한번에 걸러 낼 수 있는 불량 사용자의 조합의 개수를 구해야한다.

1. 해당 사용자를 선택했는지를 표현하기 위해 bitmasking 활용
2. 불량사용자를 검출하기 위해 re 모듈을 통해 정규표현식 활용
3. N 명의 유저로 부터 K(banned_id 개수)를 걸러내기 위해, permutation을 통해 모든 순서쌍을 비교해서, 나중에 set으로 중복되는 조합의 개수를 제거한다.

re.match

#fr*d* -> fr.d.
re.match("fr.d.",str)

Solution 1

import re
from itertools import permutations
#비트 마스킹
def str_to_bit(conversion,str):
    return 1<<conversion.index(str)  
    
def solution(user_id, banned_id):
    answer = 0
    banned_id=list(map(lambda x: x.replace("*","."),banned_id))
    banned_length=len(banned_id)
    candidates=[]
    for permutation in permutations(user_id,banned_length):
        temp=0
        ban_index=0
        match_count=0
        #각각의 순서쌍에 대해, banned_id를 통해 matching 되는 지 확인
        for str in permutation:
            while ban_index < banned_length:
                ban_id=banned_id[ban_index]
                #banned_id 패턴의 길이와 같고, 정규표현식 매칭이 되는 경우에 대해서만 확인
                if len(str)==len(ban_id) and re.match(ban_id,str):
                    #중복여부를 빠르게 처리하기 위해 bitmasking으로 bit 변환 수행
                    temp+=str_to_bit(user_id,str)
                    #중복된 banned_id 처리를 방지하기 위해 활용
                    ban_index+=1
                    #매칭되는 count 수
                    match_count+=1
                    break         
                ban_index+=1
        #banned_id 개수 만큼 매칭되는 조합에 대해서만 저장한다.
        if match_count==banned_length:
            candidates.append(temp) 
    #순서쌍을 고려했기 때문에 중복되는 조합이 발생할 수 있다.
    answer=len(set(candidates))
        
    return answer

또는 아래 처럼, 각각의 banned_id에 대해서, 매칭되는 user 목록을 저장해놓고, 이들을 product을 통해 모든 조합의 개수를 비교한느 방식을 취하는 것도 가능하다.

Solution 2

import re
from itertools import product  
    
def solution(user_id, banned_id):
    banned_id=list(map(lambda x : x.replace("*","."),banned_id))
    
    answer = set()
    result = [[] for i in range(len(banned_id))]

    for i in range(len(banned_id)):
        for u in user_id:
            if len(banned_id[i])==len(u) and re.match(banned_id[i], u):
                result[i].append(u)
    #banned_id에 대응되는 모든 유저의 조합
    for r in list(product(*result)):
        #banned_id가 각각 다른 유저와 매칭되어야한다.
        if len(set(r)) == len(banned_id):
            answer.add("".join(sorted(set(r))))
    #product이기 때문에 순서가 발생하므로 중복된 조합 발생 가능
    return len(answer)