코테 노트/프로그래머스

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

화요밍 2021. 8. 31. 03:10
728x90
반응형

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

 

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

개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량

programmers.co.kr

 

최종 풀이

 

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

프로그래머스 알고리즘 소스 코드 모음. Contribute to hwayeon351/Programmers-Algorithms development by creating an account on GitHub.

github.com

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)

참고

 

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

https://programmers.co.kr/learn/courses/30/lessons/64061?language=python3 코딩테스트 연습 - 크레인 인형뽑기 게임 [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]] [1,5,3,5,1,2,1,4] 4 pro..

hwayomingdlog.tistory.com

 

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

https://programmers.co.kr/learn/courses/30/lessons/64065?language=python3 코딩테스트 연습 - 튜플 "{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{4,2,3},{..

hwayomingdlog.tistory.com

 

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

https://programmers.co.kr/learn/courses/30/lessons/64062?language=python3 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 최종 코드 GitHub -> https://github.co..

hwayomingdlog.tistory.com

 

 

 

 

728x90
반응형