[프로그래머스] Lv3. 불량 사용자 (2019 카카오 인턴십)

🔗

풀이

불량 사용자 아이디 하나는 응모자 아이디 중 하나에 해당하고 같은 응모자 아이디가 중복해서 제재 아이디 목록에 들어가는 경우는 없습니다.

불량 사용자 아이디와 응모자 아이디는 1:1로 대치되고, 같은 아이디가 중복해서 들어가는 경우는 없으므로 둘의 개수는 같을 것이다. 불량 아이디 목록이 4개라면 그에 대응되는 응모자 아이디의 개수가 4개가 된다.

❌ 실패

각각의 불량 아이디에 해당하는 응모자 아이디들이 몇 개인지를 구한 다음 조합 구하듯이 각각의 개수를 곱해서 구했으나 실패했다.

불량 사용자 아이디와 응모자 아이디는 1:1로 대응하게 되고 중복이 없어야 하는데, 이 경우는 중복으로 들어가는 경우도 셀 수 밖에 없기 때문이다. frodo 아이디는 *rodo와 fr*d* 두 가지 불량 아이디 경우에 모두 해당되는데 실제로 구할 때는 중복이 없어야 하기 때문에 둘 중 하나의 경우에만 해당하게 구해야 한다. 하지만 아래의 코드처럼 단순 곱으로 구하게 되면 이 부분을 거를 수가 없다.

def solution(user_id, banned_id):
    banned_info = defaultdict(int)
    for i in banned_id:
        banned_info[i] += 1
    
    def find(ban, user):
        if len(ban) != len(user):
            return False
        
        lst = list(map(set, zip(ban, user)))
        for i in lst:
            if len(i) != 1 and '*' not in i:
                return False
            
        return True
        
    banned_count = defaultdict(int)
    for ban in list(banned_info):
        for user in user_id:
            banned_count[ban] += find(ban, user)
    
    answer = 1
    for key in list(banned_info):
        answer *= banned_count[key] // banned_info[key]
    
    print(banned_count, banned_info)
    return answer
    
from collections import defaultdict

⭕️ 성공

불량 아이디에 해당하는 응모자 아이디 리스트를 찾는다. 불량 아이디는 중복일 수 있으므로 a라는 불량 아이디의 응모자 아이디 리스트를 찾았다면 banned_users_lst에 데이터를 저장해둔다. 다음번 불량 아이디가 이미 앞서 찾았던 불량 아이디라면 해당 데이터를 가져와서 저장하고 없다면 찾는다.

찾은 아이디 리스트를 재귀로 탐색하며 가능한 조합인지 확인하다. 중복이 없어야하며, 1:1로 대응해야 한다. 중복되는 조합을 거를 수 있도록 조합은 정렬한 후 문자열로 대치하여 저장한다.

1. abc123 crodo frodo frodoc
2. abc123 crodo frodo frodoc
3. abc123 fradi frodo frodoc
4. abc123 fradi frodo frodoc
5. abc123 crodo fradi frodoc
6. abc123 crodo fradi frodoc

1번과 2번은 불량 아이디 ******가 2개라서 중복되는 경우이다. 이런 중복의 경우를 전부 제거하기 위해 set을 사용한다. 최종적으로 중복되는 조합이 제거되고 저장된 set의 길이만 반환한다.

def solution(user_id, banned_id):
	# 불량 아이디에 해당하는 응모자 아이디인지 확인
    def find(ban, user):
        if len(ban) != len(user):
            return []

        lst = list(map(set, zip(ban, user)))
        for i in lst:
            if len(i) != 1 and '*' not in i:
                return []

        return [user]
	
    # 불량 아이디에 해당하는 응모자 아이디들 찾기
    def find_banned_users_lst():
        banned_users_lst, banned_lst = defaultdict(list), []*len(banned_id)
        for ban in banned_id:
            if not banned_users_lst[ban]:
                for user in user_id:
                    banned_users_lst[ban] += find(ban, user)
            banned_lst.append(banned_users_lst[ban])

        return banned_lst
	
    # 가능한 조합 만들기(재귀)
    def make_combination(lst, idx, comb):
        nonlocal answer
        if idx == len(lst):
            answer.append(" ".join(sorted(comb)))
            return 

        for i in lst[idx]:
            if i not in comb:

                make_combination(lst, idx+1, comb+[i])                

    answer = []
    make_combination(find_banned_users_lst(), 0, [])
    return len(set(answer))

from collections import defaultdict