[프로그래머스] 불량 사용자 [Level 3] (python 파이썬)

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

프로그래머스

 

 

 

 

 

 

 

 

 

 

 

from collections import deque
def solution(user_id, banned_id):
    l = [[] for i in range(len(banned_id))]
    
    for i in range(len(banned_id)):
        now = banned_id[i]
        for user in user_id:
            if len(user) == len(now):
                c = 0
                for j in range(len(user)):
                    if user[j] != now[j] and now[j] != "*":
                        c = 1
                        break
                if c == 0:
                    l[i].append(user)
                    
    
    dq = []
    for i in l[0]:
        dq.append([[i],0])
    dq = deque(dq)
    ans = []
    while dq:
        
        now = dq.popleft()    
        
        if now[1] == len(banned_id)-1:
            now[0].sort()
            if now[0] not in ans:
                ans.append(now[0])
        
            
        else:
            for member in l[now[1]+1]:
                n = now[0][:]
                if member not in n:
                    n.append(member)                    
                    dq.append([n, now[1]+1])
                    
    return len(ans)

 

 

 

 

 

이 문제의 입력값 user_id 는 8 이하이며, 각 원소의 길이도 8 이하이다.

 

또한 banned_id도 8 이하이며, 각 원소의 길이도 8 이하고, 각 아이디는 알파벳 소문자 숫자 "*"로만 이루어져 있다.

 

 

이러한 문제의 입력값을 봤을 때, 가능한 경우의 수가 다른 문제에 비해 매우 적다는 점을 유추할 수 있다.

 

 

 

문제를 분석해 보자.

 

 

각각의 밴 아이디에 대해 가능한 사용자들이 있을 것이다. (*rodo = frodo, crodo ....) 

 

밴 아이디의 모음은 중복이 존재하지 않는다. (*rodo 와 또다른 *rodo 는 다른 아이디, 즉 첫 번째는 frodo, 두 번째는 crodo.. 이런 식)

 

사용자의 아이디의 모음 또한 종복이 존재하지 않는다. 

 

이 때 가능한 밴 아이디의 모음의 개수를 구하는 것이 문제이다. 

 

 

 

 

 

1. 각각의 밴 아이디에 대해 가능한 사용자 아이디의 모음을 구한다. [ [첫 번째 밴 아이디에 가능한 사용자]  , [두 번째 아이디에 가능한 사용자] .... [n 번째 아이디에 가능한 사용자] ]

 

 

 

 

2. 첫 번째  밴 아이디에 가능한 사용자를 pop해서 덱으로 만든다. ( 이를 시작점으로 해서 dfs를 수행하기 위해 )

 

2-1. 이 때 덱에 들어가는 사용자 정보는 [ [처음부터 현재 밴 아이디까지 가능한 밴 아이디에 가능한 사용자 아이디의 모음] [ n ] ] (n 은  n 번째 밴 아이디까지 [현재 어디까지 왔나] )

 

 

 

 

3. while 문 안에서 덱에서 하나씩 popleft 하면서 연산을 반복한다.

 

 

       3-1. 만약 pop한 덱이 마지막 사용자까지 돈 최종의 가능한 사용자의 경우의 수인 경우, 정렬 후 정답에 없는 경우 정답에 삽입.(문제 제한 사항 중 제재 아이디 목록들을 구했을 때 아이디들이 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리하여 하나로 새기 때문에, 정렬을 한 후 비교를 하는 방법을 이용해 아이디 목록의 내용을 비교할 수 있다. )

 

 

       3-2. n+1 번째 밴 아이디의 가능한 사용자에 대해서 

              3-2. 만약 사용자가 현재까지의 사용자의 모음에 없다면

                     3-3. 덱에 [ [현재까지에 사용자를 추가한 사용자 모음 , n+1 ] ] 삽입

 

 

 

4. while 문이 끝나고 난 후의 ans에는 가능한 아이디의 경우의 수의 모음들이 있을 것이다. 따라서 이 ans의 길이를 리턴해 주면 된다.