728x90
반응형
https://programmers.co.kr/learn/courses/30/lessons/64064?language=python#
최종 풀이
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
- 4. 호텔 방 배정 ->
- 5. 징검다리 건너기 -> https://hwayomingdlog.tistory.com/154
728x90
반응형
'코테 노트 > 프로그래머스' 카테고리의 다른 글
Level 3 경주로 건설 <2020 카카오 인턴십> Python 3 (0) | 2021.09.01 |
---|---|
Level 2 거리두기 확인하기 <2021 카카오 인턴십> Python 3 (0) | 2021.08.31 |
Level 1 크레인 인형뽑기 게임 <2019 카카오 인턴> Python 3 (0) | 2021.08.30 |
Level 3 표 편집 <2021 카카오 인턴십> Python 3 (0) | 2021.08.27 |
Level 1 키패드 누르기 <2020 카카오 인턴십> Python 3 (0) | 2021.08.24 |