레벨 1과 2를 푼다음에, 이제 레벨3을 입문하였지만,
아직 갈 길이 먼 것 같습니다. 이해를 해도 반 밖에 못하는 상황이 오네요
덕분에 이 문제를 3일 동안 붙잡았습니다.

문제 자체는 정말 간단한 편입니다.
banned_id 리스트에 해당되는 user_id에 매칭되는 경우의 수를 모두 구하는 문제입니다.
필요지식은, 순열, 정렬, 중복제거, 완전탐색 정도 입니다.

문제를 풀기 위해서는 순열과 조합에 대한 차이를 알아보아야합니다.

순열은 어떤 리스트에서 순서를 고려해서 나올 수 있는 경우의 수라고 보시면 이해하기 쉽습니다.
조합은 어떤 리스트에서 순서를 고려하지 않고 나올 수 있는 경우의 수 입니다.

단지 순서를 고려하고 고려하지 않는다의 차이 밖에 없습니다.
예를 한 번 들어봅시다.

배열 1)

위의 배열에서 순열을 만들어 보겠습니다.
[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]

마찬 가지로 조합을 만들어 보겠습니다.
[1, 2], [1, 3], [2, 3]

순열은 숫자의 위치가 바뀌어도 다른 것으로 인식하고, 조합은 순서상관없이 안의 요소만 같으면
같은 것이라고 인식합니다.

이 문제는 조합보다는 순열이 필요한 문제입니다. 그 이유는 뒤에서 천천히 풀어보도록 합시다.

여기서 꼭 알아야하는 요소들을 살펴봅시다.

1. user_id에는 절대로 같은 요소가 존재하지 않는다.
2. 반대로 banned_id에는 같은 요소가 존재 할 수 있다.

위의 두 가지 요소들은 문제를 풀기위해서는 확실히 이해하셔야하는 부분입니다.

우리가 원하는 답은 banned_id에 대응되는 user_id에 대한 경우의 수를 찾는 것입니다.
그러면 당연히 우리가 찾는 순열의 길이는 banned_id와 일치 해야한다는 점입니다.

예를 들어봅시다.

user_id

banned_id

banned_id의 길이는 총 2입니다. banned_id에 대응되는 user_id의 경우의 수를 구하는 것이 정답이라고 하였습니다.
위의 banned_id의 길이는 두 가지 요소밖에 존재하지 않아 2가 됩니다. 그럼 당연히 user_id에서 2가지로 나올 수 있는
모든 경우의 수를 구해서 비교해야합니다.

["dao", "dizini"], ["dao", bazzi"], ["dizini", "dao"], ["dizini", "bazzi"], ["bazzi", "dao"], ["bazzi", "dizini"]

위와 같은 순열을 우리는 구성할 수 있습니다.
위의 순열을 banned_id인 "d*o" 와 "b*zz*"에 매칭 시키면

["dao", "bazzi"]
총 6가지의 경우의 수 중 위의 1가지가 매칭됩니다.
이제 여기서 문제를 해결하시지 못하신 분들은 이해력이 부족하실 겁니다.
이 부분이 이 문제의 하이라이트 입니다. 다들 왜 ["bazzi", "dao"]도 해당되는데 왜 그건 포함이 안되냐
하실 수 있는 부분입니다.
아까도 말씀드렸다시피 이 문제는 조합이 아닌 반드시 순열을 사용해야 푸실 수 있는 문제라고 하였습니다.

왜 그러면 안되는 가에 대해 간단히 알아봅시다.

user_id

banned_id

(아.. 고추마요치킨 먹고싶다 ...ㅡㅡ)

각설하고, user_id에서 조합을 한 번 구해봐야겠습니다.

1 - ["prodo", "piodi", "proda"], 2- ["prodo", "piodi", "pradak"], 3 - ["piodi", "proda", "pradak"]

총 위와 같이 3가지의 조합이 나옵니다. (사실은 4가지 조합이지만 이해만 하시라고 제외시켰습니다.)
위 조합을 그대로 하나씩 매칭시켜서 banned_id를 없애는 방향으로 구해보면
사실 2번과 3번은 둘 다 매칭이 가능하지만 2번의 경우에는 먼저 prodo를 매칭시킬경우
"p*od*"와 "prod*" 중에 하나를 선택해야합니다. 근데 특별한 지정이 없으면 제일 앞쪽의 경우를 우선 선택할겁니다.
그럼 "prod*"만 남게되는데, 다음 문자인 "piodi"는 원래 매칭이 될 수 있었음에도 불구하고, 앞의 사용자때문에
매칭이 실패됩니다. 이런 경우가 존재하기 때문에 순서를 고려하지 않은 경우인 조합이 사용되는 것이 아닌
순서를 고려하는 순열을 사용하게 됩니다. 순열을 매칭시키면 가능한 모든 순서의 경우의 수를 매칭시키므로
위와 같은 상황이 발생하여도 같은 사용자이지만 순서가 다른 경우도 매칭할 수 있습니다.
*이 존재하기 때문에 banned_id에는 어떤 user_id가 매칭되는지 경우의 수는 알 수 있지만,
정확한 값을 매칭시킬 수는 없는거죠.

따라서, user_id에 대해 banned_id의 길이를 가지는 모든 순열을 구한 후에
banned_id와 같은지 판별하면 됩니다.

그렇지만 순열을 사용하면, 중복된 값이 생길 수 밖에 없습니다.
새로운 예를 들어봅시다.

user_id

banned_id

위와 같은 경우에서 보면, user_id의 순열의 일부만 구해보자면

["aa", "ab", "cc"], ["ab", "aa", "cc"]

위의 순열을 보면, 매칭시키면 둘 다 매칭이됩니다.
그렇지만 이 문제에서는 위와 같은 경우는 같은 경우라고 봐야합니다.
매칭이 안되는 경우를 탐색하기 위해서 순열을 사용하였으면 그 뒷처리 또한 필요하겠죠.
그 경우가 위와 같은 경우가 됩니다. 둘 다 매칭이 되지만, 둘 다 같은 경우죠.
이런 경우는 간단합니다. 답이 될 수 있는 모든 순열을 어떤 변수에 저장한 뒤에
해당 순열들을 전부 정렬시킨후에, 같은 값들을 제거하면 됩니다.

["ab", "aa", "cc"] 오름차 정렬시키면, ["aa", "ab", "cc"]와 같습니다.
즉, 같은 요소이면 전부 같은 값을 가지도록 만들어서 중복값을 제거하는 원리입니다.
그러면 2개가 매칭되는 것을 알 수 있지만, 결론은 중복을 제거함으로써 1개의 경우만 매칭이 됩니다.
주의할 점은 처음부터 정렬하면, banned_id와 매칭시킬 수 없으므로 반드시
매칭되는 순열을 전부 구한 후에 정렬 후에 중복제거를 실시해야 올바른 결괏값을 얻을 수 있습니다.

파이썬을 사용하시는 분들은
itertools 라이브러리의 permutations에 대해 검색해보시면
손쉽게 순열을 구하는 방법을 알 수 있습니다.

from itertools import permutations

위와 같은 방식으로 라이브러리를 불러오고

all_list = permutations(user_id, len(banned_id))

위와 같은 방식으로 user_id에 대해 banned_id의 길이만큼에 해당되는 모든 순열을 구할 수가 있습니다.

또한 라이브러리 사용이 싫으시면 dfs를 활용한 방법을 사용 할 수 있습니다.

user_id = ["aaa", "bbb", "ccc"]
outlist = []
def dfs(user_id, visited, now_list, outlist, n):
    if len(now_list) == n:
        outlist.append(now_list)
        return
    for i in range(len(user_id)):
        if not visited[i]:
            new_list = now_list.copy()
            new_visited = visited.copy()
            new_list.append(user_id[i])
            new_visited[i] = True
            dfs(user_id, new_visited, new_list, outlist, n)
dfs(user_id, [False]*len(user_id), [], outlist, 3)
for o in outlist:
    print(o)

위의 코드는 dfs로 순열을 구하는 방법 예시입니다.(참고용으로만 봐주세요)

순열을 구하였으면 해당 순열이 banned_id에 매칭이 되는지 확인이 필요합니다.
이 부분은 너무 쉬우므로, 넘어가도록 하겠습니다, 어렵다고 느껴지시면, 레벨2부터 다시 풀어보시면 도움이 될겁니다.

마지막 부분은 정렬 후, 중복제거입니다.
아마 set()자료형을 통해 중복제거를 해보신분들을 아시겠지만,
파이썬은 list[]자료형을 set에 포함시킬 수가 없습니다.
파이썬을 사용하는 분에게만 해당되는 내용이지만,
set()은 list[]자료형은 못 가지지만 tuple()자료형은 가질 수 있습니다.
따라서 매칭되는 배열을 answer_list라고 가정하면,,,

answer_list = list(set(map(tuple, answer_list)))

위와 같이 일시적으로 map함수를 통해 list자료형을 tuple로 변환 시킨 뒤에 set을 통해
중복제거 후 다시 list로 반환시켜줄 수 있습니다.

이 방법을 거치고 나면, answer_list의 길이가 곧 banned_id와 매칭될 수 있는 모든 경우의 수라고 볼 수 있습니다.

내용이 길었지만, 어떤 분들에게는 도움이 되었으면 하는 바람입니다.
물론, 다른 분들이 올린 해설도 훌륭하지만, 기본적으로 알아야하는 지식을 건너뛴채로
이 문제를 도전하시는 분들이 쉽게 이해할 수 있도록 도움을 주고 싶었습니다.

즐거운 코딩 되세요~