【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, [])
