【Algorithm】불량 사용자 - 카카오 문제

프로그래머스 불량사용자 알고리즘 풀이

문제링크 : 불량사용자
주석을 참고해서 코드 이해에 도움을 받으시길 바랍니다.

풀이 코드

"""
Point
    - def(A) 내부에 다시 def(B)을 사용함으로써, 전역변수나 함수(B)의 많은 매개변수 사용을 줄였다.
    - banned_id 원소 하나 당, 매핑이 되는 user_id 하나를 골라낸다.
"""

def solution(user_id, banned_id):
    
    def check(b_id, user):
        """
        하나의 user_id와 b_id를 비교한다. 
        user_id가 b_id에 속하는 것이라면, return True.
        아니라면, return False. 
        """
        for s in range(len(b_id)):
            if b_id[s] != '*':
                if b_id[s] != user[s]:
                    return False
            elif b_id[s] == '*':
                continue
        else:
            return True

    def back(u, b):
        if b == N2: # Reculsivd Function의 Base condition이다. "user_id 하나와 banned_id 모두를 다 비교했다면."
            if u not in result:
                result.append(u[:]) # u를 copy by value해서 result 에 넣는다. **중요**
            return
        for i in range(N1): # user_id의 원소를 하나씩 살펴본다. 
            # 위에서 고른 user_id의 하나와, banned_id의 원소 모두와 비교해본다.
            if u[i] == 0 and len(banned_id[b]) == len(user_id[i]): # 중요한 전제 조건. 2 문자열의 길이가 같아야 한다. 
                if check(banned_id[b], user_id[i]) == True: # banned_id 원소 하나 당, 매핑이 되는 user_id 하나를 골라냈다면, 
                    u[i] = 1 # 위에서 매핑한 user_id임을 표기해논다.
                    back(u, b + 1) # 다음 banned_id 원소에, 매핑되는 user_id 하나를 골라낸다.
                    u[i] = 0 # 맨 처음부터 원상 복귀.

    # 1 : 변수 선언 및 정의
    answer = 0
    N1 = len(user_id)
    N2 = len(banned_id)
    u = [0 for ii in range(N1)]  # u[k]=1 는 user_id[k]가 banned_id 중 하나에 해당함을 의미한다. 
    result = [] # 가능한 u 배열의 경우와 수를 저장한다. 

    # 2 : reculsive 돌기 시작!
    back(u, 0)

    # 3 : 최종 결과 return.
    answer = len(result) # 입출력 예 1의 result = [[1,0,0,1,0] , [0,1,0,1,0]]. 즉 2가지 경우가 존재한다.
    return answer

if __name__ == "__main__":
    user_id = ["frodo", "fradi", "crodo", "abc123", "frodoc"]
    banned_id = ["fr*d*", "abc1**"]
    print(solution(user_id, banned_id))
    pass


"""
Reculsive 흐름도 
[1, 1, 0, 0, 0]
[1, 0, 1, 0, 0]
[0, 0, 0, 1, 0]
[1, 0, 0, 0, 1]
[0, 0, 0, 0, 0]
[0, 1, 1, 0, 0]
[0, 1, 0, 1, 0]
[0, 1, 0, 0, 1]
[0, 0, 0, 0, 0]
[0, 0, 1, 1, 0]
[0, 0, 1, 0, 1]
[0, 0, 0, 0, 0]
[0, 0, 0, 1, 1]
[0, 0, 0, 0, 0]
"""

참고할 만한 다른 사람 코드

"""
우선 와일드카드가 포함된 문자(banned_id)로 가능한 모든 user_id의 idx를 추출한다.
이를 가지고 완전 탐색 방법을 이용하여 답을 구한다
"""

import re

def solution(user_id, banned_id):
    possible_id = []   # 각 banned_id로부터 가능한 user_id들의 index들이 저장될 배열
    cases_arr = []     # 모든 정답들을 저장할 배열
    len_banned_id = len(banned_id)  #

    def calc_cases_idx(id): # 가능한 모든 경우의 수를 추출하는 함수
        id+="$"
        regex = re.compile(id.replace('*', '.'))
        matches = [i for i, string in enumerate(user_id) if re.match(regex, string)]
        return matches
    
    def recSolution(n, arr): #현재 몇번째 banned_id인지, 어떠한 user_id들이 선택되었는지에 대한 배열
        if n == len_banned_id:
            arr.sort()
            if arr not in cases_arr:
                cases_arr.append(arr)
                return 1
            else:
                return 0
        rec_answer = 0
        for num in possible_id[n]:
            if num not in arr:
                rec_answer += recSolution(n+1, arr + [num])
                
        return rec_answer
    
    for i in range(len(banned_id)):
        possible_id.append(calc_cases_idx(banned_id[i]))
    print(possible_id)
    
    
    return recSolution(0, [])

© All rights reserved By Junha Song.