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

문제

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

프로그래머스

 

풀이

1. itertools의 permutations를 사용해 banned_id의 개수만큼의 모든 경우의 수를 만들어낸다.
   (user_id의 길이 제한이 8까지 밖에 안되기 때문에 가능함)
2. 생성된 조합에 대해 각 원소가 banned_id의 조건과 일치하는지 여부를 따지고, 모두 해당될 경우에 가능한 경우의 수로 추가한다.
   1. combinations가 아닌 permutations를 사용했기 때문에 동일한 결과가 중복되어 추가될 수 있으므로,
      추가하는 과정에서 중복 여부를 파악해 추가한다.
3. 정답이 될 수 있는 모든 경우의 수를 return

def solution(user_id, banned_id):
    answer=0
    import re
    from itertools import permutations
    # 모든 조합 구하기
    answers = []
    for p in permutations(user_id, len(banned_id)):
        cnt = 0
        for i in range(len(p)):
            ban = banned_id[i].replace('*','.')
            if re.match(ban,p[i]) and len(ban)==len(p[i]):
                cnt+=1
        if cnt==len(banned_id):
            p = sorted(p)
            if p not in answers:
                answers.append(p)
                
    answer = len(answers)
    
    return answer

 

DFS/BFS를 활용해서 모든 경우의 수를 구하는 방법도 시도 가능할 것으로 보임