Level 3 불량 사용자 <2019 카카오 인턴십> Python 3

https://programmers.co.kr/learn/courses/30/lessons/64064?language=python# 

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

 

최종 풀이

• GitHub -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_불량사용자.py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

from itertools import permutations
def solution(user_id, banned_id):
    ans_set = set()
    permu = permutations(user_id, len(banned_id))
    for p in permu:
        check = True
        for i, user in enumerate(p):
            if not check: break
            if len(user) != len(banned_id[i]): 
                check = False
                break
            for u, b in zip(user, banned_id[i]):
                if b == '*' or b == u: continue
                check = False
                break
        if check: ans_set.add("".join(sorted(list(p))))
    return len(ans_set)

---

풀이 과정

1. 

from itertools import permutations
def solution(user_id, banned_id):
	#제재 아이디 목록
    ans_set = set()
    
    #가능한 모든 후보 제재아이디 목록
    permu = permutations(user_id, len(banned_id))
    
    #각각의 후보가 제재아이디 목록이 될 수 있는지 판별
    for p in permu:
    	#check가 True이면 현재 후보가 제재아이디 목록이 될 수 있다
        check = True
        
        for i, user in enumerate(p):
        	#이전 응모자 아이디가 불량사용자 아이디와 일치하지 않은 경우, 현재 경우의 수는 후보가 될 수 없다
            if not check: break
            
            #현재 응모자 아이디의 길이가 불량사용자 아이디의 길이와 다른 경우, 제재아이디가 아니다 -> 현재 경우의 수는 후보가 될 수 없다
            if len(user) != len(banned_id[i]): 
                check = False
                break
            
            #현재 응모자 아이디가 제재아이디가 될 수 있는지 판별
            for u, b in zip(user, banned_id[i]):
                if b == '*' or b == u: continue
                check = False
                break
        #현재 후보가 제재아이디 목록이 될 수 있는 경우, 현재 후보의 아이디 목록을 정렬하여 문자열로 변경하여 ans_set에 추가 
        if check: ans_set.add("".join(sorted(list(p))))
    return len(ans_set)
#시간복잡도 = O(len(user_id)!*len(user_id)*len(user_id[i])) = O(n!), 공간복잡도 = O(n!)
#최악의 경우, len(user_id) = 8, 모든 유저 아이디의 길이(user_id[i]) = 8, len(banned_id) = 8, 모든 불량사용자 아이디의 길이(banned_id[i]) = 8, 모든 banned_id = '********'
#최대 연산 횟수 = 8! * 8 * 8 = 2,580,480번

 

2. 

from itertools import combinations
def dfs(i, ban_set, ban_dict, visit, total, ids):
    global kinds
    #total만큼 제재아이디를 뽑은 경우, 함수 종료
    if len(ids) == total:
        #중복을 없애기 위해 리스트 ids를 정렬한 후, 문자열로 만들어 kinds에 추가
        kinds.add("".join(sorted(ids)))
        return
    
    #제재아이디 뽑기 - ban_dict의 key 종류 별로 뽑아야 하는 수 ban_dict[key][0]만큼 뽑는다
    for ii in range(len(ban_set)):
        #key = ii번째 불량사용자 아이디에 해당하는 제재아이디를 뽑지 않은 경우, 제재아이디를 뽑는다
        if not visit[ii]:
            visit[ii] = 1
            #ban_id = 불량사용자 아이디, num = 뽑아야하는 제재아이디 수, user_ids = ban_id에 해당하는 제재아이디 후보
            ban_id = ban_set[ii]
            num = ban_dict[ban_id][0]
            user_ids = ban_dict[ban_id][1]
            
            #user_ids 중에 num개를 뽑는 조합
            combi = combinations(user_ids, num)
            for c in combi:
                for id in c:
                    #후보 제재아이디 목록 c 중에 이전에 이미 뽑힌 제재아이디 ids에 속한 요소가 있는 경우, c는 제재아이디 목록이 될 수 없다
                    if id in ids: 
                        break
                else:
                    #후보 제재아이디 목록 c가 제재아이디 목록에 속할 수 있는 경우, ids에 추가하고 dfs 탐색을 이어간다
                    for id in c: ids.append(id)
                    dfs(i+1, ban_set, ban_dict, visit, total, ids)
                    for _ in range(len(c)): ids.pop()
            visit[ii] = 0

def solution(user_id, banned_id):
    #1. ban_dict 구성하기
    #ban_dict[ban_id] = [num, user_ids]
    #num = ban_id에 해당하는 유저아이디를 뽑아야하는 개수
    #user_ids = ban_id에 해당하는 유저아이디들을 담은 리스트
    ban_dict = dict()
    for ban in banned_id:
        b_id = str(ban)
        if b_id not in ban_dict:
            ban_dict[b_id] = [1, []]
        else: ban_dict[b_id][0] += 1
    ban_set = ban_dict.keys()
    
    #2 ban_dict에 user_id 분류하기
    for user in user_id:
        for ban in ban_set:
            #아이디 user가 제재아이디 ban이 될 수 있는지 체크
            if len(user) != len(ban): continue
            for b, u in zip(ban, user):
                if b == '*' or b == u: continue
                break
            #아이디 user가 제재아이디 ban이 될 수 있는 경우, ban_dict에 추가
            else:
                ban_dict[ban][1].append(str(user))
    
    #3 경우의 수 구하기
    global kinds
    kinds = set()
    
    #총 뽑아야 하는 제재아이디 수
    total = 0
    for ban in ban_set:
        total += ban_dict[ban][0]
    
    #제재아이디 뽑기
    for i in range(len(ban_set)):
        visit = [0]*len(ban_set)
        dfs(i, ban_set, ban_dict, visit, total, [])
    
    return len(kinds)

---

참고

• 1.크레인 인형뽑기 게임 -> https://hwayomingdlog.tistory.com/142

Level 1 크레인 인형뽑기 게임 <2019 카카오 인턴> Python 3

• 2. 튜플 -> 2021.09.06 - [코테 노트/프로그래머스] - Level 2 튜플 <2019 카카오 인턴십> Python 3

Level 2 튜플 <2019 카카오 인턴십> Python 3

• 4. 호텔 방 배정 -> 
• 5. 징검다리 건너기 -> https://hwayomingdlog.tistory.com/154

Level 3 징검다리 건너기 <2019 카카오 인턴십> Python3