[Level 3] 불량 사용자

https://programmers.co.kr/learn/courses/30/lessons/64064

코딩테스트 연습 - 불량 사용자

---

접근

먼저 각각의 banned_id가 될 수 있는 아이디를 찾는다. 이후 불량 사용자가 될 수 있는 조합을 찾는다.

 

구현

- names 배열에 해당 banned_id가 될 수 있는 아이디를 담는다. 

- banned_id를 순차적으로 탐색하여 아이디를 찾는데 길이가 같을 때에 아이디를 비교한다.

- 별표(*)가 있을 때는 아무 문자나 올 수 있기 때문에 continue, 아이디가 같을 때도 continue, 하지만 다를 때는 flag를 False로 변경 후 종료한다.

    names = [[] for _ in range(len(banned))]

    for i in range(len(banned)):
        for j in range(len(user)):
            if len(banned[i]) == len(user[j]):
                flag = True
                for k in range(len(user[j])):
                    if banned[i][k] == '*':
                        continue
                    else:
                        if banned[i][k] == user[j][k]:
                            continue
                        else:
                            flag = False
                            break
                if flag:
                    names[i].append(user[j])

- combi에 만들어진 조합을 추가한다.

- 각각의 banned_id가 될 수 있는 이름들을 picked에 추가하고

- n개를 선택했을 때 picked를 정렬하여 위치만 다른 조합들을 동일하게 만들어준다.

- 이를 key로 설정하여 combi 안에 없다면 최종해를 증가시키고 combi에 추가한다.

    combi = set()
    def dfs(next, picked, n, names):
        nonlocal answer, combi
        if next == n:
            new_picked = sorted(picked)
            key = ''.join(new_picked)
            if key not in combi:
                answer += 1
                combi.add(key)
            return

        for i in range(len(names[next])):
            if names[next][i] in picked:
                continue
            picked.append(names[next][i])
            dfs(next+1, picked, n, names)
            picked.pop()

    for i in range(len(names[0])):
        picked = [names[0][i], ]
        dfs(1, picked, len(names), names)

---

전체 코드

def solution(user, banned):
    answer = 0
    names = [[] for _ in range(len(banned))]

    for i in range(len(banned)):
        for j in range(len(user)):
            if len(banned[i]) == len(user[j]):
                flag = True
                for k in range(len(user[j])):
                    if banned[i][k] == '*':
                        continue
                    else:
                        if banned[i][k] == user[j][k]:
                            continue
                        else:
                            flag = False
                            break
                if flag:
                    names[i].append(user[j])
                    
    combi = set()
    def dfs(next, picked, n, names):
        nonlocal answer, combi
        if next == n:
            new_picked = sorted(picked)
            key = ''.join(new_picked)
            if key not in combi:
                answer += 1
                combi.add(key)
            return

        for i in range(len(names[next])):
            if names[next][i] in picked:
                continue
            picked.append(names[next][i])
            dfs(next+1, picked, n, names)
            picked.pop()

    for i in range(len(names[0])):
        picked = [names[0][i], ]
        dfs(1, picked, len(names), names)
    
    return answer