2019 카카오 개발자 겨울 인턴십에 출제된 백트래킹 문제이다.
주어지는 입력값의 크기가 크지 않아, 완전탐색으로도 풀린다고 들었지만 백트래킹이 정석인 문제라고 생각한다.
def solution(user_id, banned_id):
def is_match(user, banned_user):
if len(user) != len(banned_user):
return False
for i in range(len(user)):
if banned_user[i] != '*' and banned_user[i] != user[i]:
return False
return True
def back_tracking(depth, selected):
if depth == len(banned_id):
result_set.add(frozenset(selected)) # 순서가 다른것도 중복으로 인식하도록 frozenset 사용
return
for user in user_id:
if user not in selected and is_match(user, banned_id[depth]):
selected.add(user)
back_tracking(depth + 1, selected)
selected.remove(user)
# set으로 바꿔 중복 제거 (순서만 다른 조합들)
result_set = set()
back_tracking(0, set()) # not in 연산 효율성을 위해 set 선택(key로 접근하는 O(1)), 리스트는 O(N)
return len(result_set)
banned_id의 조건에 일치하는 사용자 조합을 전부 만들어야 한다.
banned_id는 user_id 의 길이보다 짧거나 같고, banned_id와 매핑되는 user_id는 1개씩이니 최대 depth는 len(banned_id)로 한다.
단 백트래킹 진행 중 순서만 다른 같은 조합이 나올 수 있는데, 이것은 맨 마지막에 set()으로 집합화 시켜서 중복을 제거해주되,
순서만 다른 조합을 같은 요소라고 인식할 수 있도록 result_set에 넣을 때 frozenset()으로 감싸서 넣어준다. frozenset()은 immutable객체로써 set()의 요소로 사용할 수 있고, 순서만 다른 요소를 같은 요소라고 인식하기 때문에 set()으로 중복을 제거하기 용이하다.
또한 back_tracking의 2번째 인자인 selected를 set()으로 넣어주고 있는데, 이것은 not in 연산을 빠르게 하기 위해서이다. list를 넣을 경우 not in 조건 검사를 할 때마다 O(N)의 연산이 일어나고, 백트래킹의 재귀 방식 특성 상 해당 조건을 엄청나게 많이 검사하게 된다. 이때 list가 아닌 set을 사용하면, set은 내부적으로 해시 테이블을 사용하기 때문에 O(1) 즉 상수 시간에 탐색할 수 있다.
마지막으로, len(result_set)을 리턴함으로써 만들어진 경우의 수 개수를 리턴해주면 된다.