[2019카카오] 불량 사용자

문제 설명

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

프로그래머스

문제 풀이

• 불량 사용자 id에 해당 할 수 있는 유저 id를 전체적으로 다 찾아봄(해당 하는 유저id의 인덱스를 gr[불량사용자 인덱스]에 넣어줌)
• 그 뒤 bfs 방식으로 모두 탐색
• 제제 아이디 목록들을 구했을 때 순서와 관계없이 동일하면 같은 것으로 처리하기 때문에 집합으로 체크해줌

소스 코드 

from collections import deque

def solution(u_id, b_id):
    answer = []
    n = len(b_id)
    kk = len(u_id)
    gr = [[] for i in range(n)]
    for i in range(n):	#불량 사용자일 수 있는 user_id 찾기
        cur = b_id[i]
        m = len(cur)
        for j in range(kk):
            if(len(u_id[j])!=m): #글자 수가 다르면 그 유저는 해당x
                continue
            z = False	#해당 유저가 불량이라면 z는 False로 남아서 gr에 넣어질 예정
            for k in range(m):
                if(cur[k]=="*"):	# "*"은 모든 글자 들어오므로 continue
                    continue
                if(u_id[j][k]!=cur[k]):	#중간에 다르다면 z는 True로 변한 후 탈출(다른 것이므로)
                    z=True
                    break
            if(z==False):
                gr[i].append(j) #z가 False로 유지 된다는 것은 그 유저는 제재일 가능성이 있다는 것
    q = deque()
    for i in gr[0]:
        q.append((1,[i]))	#다음으로 체크할 불량 아이디 index와 제재 아이디를 넣음
    
    while(q):
        num, cur = q.popleft()
        if(num==n):
            answer.append(cur)
            continue
        for i in gr[num]:
            if i in cur:
                continue
            else:
                q.append((num+1,cur+[i]))
    a = set([tuple(set(item))for item in answer]) 	#집합으로 중복 체크
    return len(a)