문제
https://programmers.co.kr/learn/courses/30/lessons/64064
개요
입력으로 "*" 처리 된 불량 사용자와 실제 유저들의 아이디 목록을 받는다.
그런 다음 불량 사용자가 될 수 있는 유저들의 아이디를 매칭해서 서로 다른 가능한 조합의 개수를 세는 문제이다.
예를 들면 [a*cd, ab*d], [abcd, abxd, abvd] 이렇게 입력이 들어오면 가능한 조합의 개수는
(abcd, abxd) (abcd, abvd) (abxd, abvd)로 총 3개이다.
문제풀이
처음에는 바로 백트래킹의 풀이 방법이 떠올랐다. (여기까진 좋았다.)
그런데 풀다보니 문제에서는 (ABC, XYZ) 와 (XYZ, ABC)를 같은 데이터로 보기 때문에 중복을 제거 해야하는걸 알게 됐다.
이는 DFS 풀이에서 많이 나오는 유형이다.
순서가 뒤바뀌어도 내용이 같으면 같은 데이터로 보는 작업을 비트마스킹과 딕셔너리(Hashmap)로 해결 해주었다.
예를 들면 user_id의 길이를 3이라고 하고 user_id[0]과 user_id[1]이 불량사용자 후보가 되면 "011"로 표현하는 방식이다. 어차피 순서에 상관없이 같은 아이디가 들어오면 비트마스킹 해준 값은 항상 같을 것이므로 결과값의 중복을 쳐낼 수 있다.
하지만 내 소스는 결과값의 중복을 제거하는것 보다 더 큰 문제가 있었다.
테스트케이스5에서 계속 TLE를 받아서 코드를 꽤 오랫동안 수정했다.
백트래킹도 맞고 결과값의 중복을 제거하는것도 맞았으나 백트래킹 재귀함수 내부 로직에서 불필요한 경우의 수를 너무 많이 구하고 있었다.
나는 백트래킹 로직에서 한번의 콜스택마다 이중포문을 사용해 모든 차단아이디 -> 모든 유저아이디 순서로 탐색했다.
그런데 이렇게 하면 콜스택마다 불필요한 탐색을 반복하게 된다.
어떤 콜스택에서 불량사용자와 유저아이디 매칭을 성공하고 다음 콜스택으로 넘어가면 그 콜스택에서는 무조건 다시 차단아이디[0] 부터 끝까지 탐색을 시도하게 된다. 여기서 조건문을 잘 처리해줘도 이미 사용된 차단아이디를 탐색한다는 부분에서 시간이 낭비된다.
그러면 이중포문에서 차단아이디 포문의 range 시작 인덱스를 +1 해서 다음 콜스택에서는 무조건 인덱스상으로 그 다음 차단아이디 부터 탐색한다고 하면 괜찮을까??
이 문제와 별개로 단순 예시를 들어서 설명해보겠다.
[a,b,c,d,e,f] 라는 리스트 X가 있다.
이 때 이 X를 전부 탐색하는 for 문을 백트래킹 로직에 써주면 한번의 콜스택마다 무조건 a~z 까지 탐색을 하게 되어 있다.
인덱스를 조정해줬고 깊이우선탐색이기 때문에 abcdef가 가장 먼저 리턴될 것이고 그 다음으로는 e 콜스택에서 e->f가 되고 다음 콜스택으로 넘어가서 abcdff를 리턴하게 된다.
여기서 문제가 생긴다.
1. 차단된 아이디는 모두 매칭이 되어야 함 (e의 손실)
2. 인덱스를 조정 해줬지만 결국엔 탐색 범위를 조정 해준것이므로 한번의 콜스택에서 불필요한 여러개의 아이디를 탐색한다.
내가 원하는건 콜스택에서 차단아이디를 받으면 그 차단아이디는 그 콜스택에서만 관리되고 다른 콜스택에서는 또 다른 차단아이디만을 관리하는 방식이었는데 range의 시작 인덱스를 조정해줘도 결국 for문이기 때문에 하나의 콜스택에서는 여러개의 차단아이디를 탐색하게 된다.
그래서 이 문제는 애초에 이중포문을 쓰는 문제가 아니라 콜스택의 깊이를 banned_id 리스트의 인덱스로 활용하여 하나의 콜스택에서는 하나의 차단아이디만 가지고 탐색할 수 있게끔 구현 해야한다. (재귀 함수에서 콜스택은 깊이로 구분하기 때문에 콜스택의 깊이는 unique value이다.)
그리고 이러한 방식은 조합이라고 생각했던 이 문제가 사실은 순열문제였고 나는 순열을 DFS로 구현 해준 것이다.
그래서 itertools 라이브러리의 permutation으로 풀어도 이 문제는 해결된다.
정리하자면,
하나의 불량 사용자 정보는 여러개의 유저 아이디와 매칭될 수 있다.
순서를 고려해야 한다는 의미에서 순열이 아니라 하나의 불량 사용자 정보에 모든 유저아이디를 매칭 시켜봐야 한다는 점에서 순열 문제이다.
이는 유저 아이디가 모든 위치에 한번씩 들어갈 수 있는 경우의 수를 고려하고 각각의 경우의 수마다 모든 유저아이디가 불량 사용자와 매칭이 되는지 안되는지 판단한다는 의미다.
"위치"는 "불량 사용자"이고 "유저 아이디"가 어떤 "위치"에 들어갈 수 있을지 모르기 때문에 모든 "위치"에 유저 아이디를 두고 탐색을 해야한다.
앞으로는 DFS/백트래킹 문제에서 콜스택에서 for문을 쓰게 되면 항상 새로운 콜스택에선 새로운 for문으로 항상 처음부터 시작한다는걸 잘 생각하고 문제를 풀어야겠다.
그리고 순열을 순서가 있는 순서쌍이라고 생각하기 보다는
permutation 그 자체로 생각하고 어떤 값이 모든 자리에 한번씩 들어갈 수 있는 경우의 수라고 생각하자.
마지막으로 순열을 DFS로 구할 때 콜스택의 깊이를 자리라고 생각하자.
그 다음, 들어가는 값들에 대한 for문만 돌려주고 이미 들어간 값은 예외처리만 해주면서 끝까지 도달하면 기저조건에서 return 할 수 있게끔 구현하자.
코드
from collections import defaultdict
def find(banned,user):
if len(banned) != len(user):
return False
for i in range(len(banned)):
if banned[i]=="*":continue
elif user[i]!=banned[i]:
return False
return True
def backtrk(d, bidx, user_id, banned_id, vistB, vistU, avoidDup, avoidDupDict):
global ans
if d == len(banned_id):
if avoidDupDict[avoidDup]==0:
avoidDupDict[avoidDup]=1
ans+=1
return
# 순열 : 한명의 불량 사용자당 가능한 아이디를 탐색, 깊이가 불량사용자의 인원수만큼 들어가게 되면 모든 불량 사용자의 아이디 매칭 완료 됐다는 의미
# 백트래킹으로 다시 빠져 나와서 한명의 불량 사용자에 대한 또 다른 가능한 유저 아이디 추출함.
# 하나의 콜스택에서는 하나의 불량 사용자만 다뤄야 함. 하나의 콜스택에서 여러명의 불량사용자를 다루면 안됨. 이러면 거듭제곱꼴 형태가 됨.
bb=banned_id[bidx]
for u in range(len(user_id)):
if not vistU[u] and find(bb, user_id[u]): # 이미 사용된 아이디, 아이디 형식 확인
vistU[u]=1
backtrk(d+1, bidx+1, user_id, banned_id, vistB, vistU, avoidDup|(1<<u), avoidDupDict)
vistU[u]=0
def solution(user_id, banned_id):
global ans
ans = 0
vistU=[0]*len(user_id)
vistB=[0]*len(banned_id)
avoidDupDict = defaultdict(int)
backtrk(0, 0, user_id, banned_id, vistB, vistU, 1<<len(user_id), avoidDupDict)
return ans
print(solution(["aaaaaaaa", "bbbbbbbb", "cccccccc", "dddddddd", "eeeeeeee", "ffffffff", "gggggggg", "hhhhhhhh"],
["********","********","********","********","********","********","********","********"]))
print(solution(["frodo", "fradi", "crodo", "abc123", "frodoc"], ["fr*d*", "abc1**"]))
print(solution(["frodo", "fradi", "crodo", "abc123", "frodoc"], ["*rodo", "*rodo", "******"]))
print(solution(["frodo", "fradi", "crodo", "abc123", "frodoc"], ["fr*d*", "*rodo", "******", "******"])).JPG)