[2019 카카오 겨울 인턴십] 불량 사용자

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

Github Link : https://github.com/yuseon27/Algorithm_Practice/blob/master/Kakao/2019_winter_internship/03.%20bad_user.py

[문제 설명]

user_id와 banned_id가 주어졌을 때, 당첨에서 제외되어야 할 제재 아이디 목록의 가능한 경우의 수를 구하세요. banned_id에서  *은 어떠한 문자가 있음을 의미합니다.

 

[입력 예제]

user_id : ["frodo", "fradi", "crodo", "abc123", "frodoc"]

banned_id : ["fr*d*", "*rodo", "******", "******"]

[결과]  2

[제한 사항]

• user_id 배열의 크기는 1 이상 8 이하입니다.
• user_id 배열 각 원소들의 값은 길이가 1 이상 8 이하인 문자열입니다.
• banned_id 배열의 크기는 1 이상 user_id 배열의 크기 이하입니다.
• banned_id 배열 각 원소들의 값은 길이가 1 이상 8 이하인 문자열입니다.
• 제재 아이디 목록들을 구했을 때 아이디들이 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리하여 하나로 세면 됩니다.

 

[문제 해결]

사용한 라이브러리

• re : banned_id의 조건을 만족하는 user_id의 리스트를 구했다.
• itertools.product : banned_id별 가능한 아이디들의 리스트의 조합을 구했다.

 

알고리즘

1. banned_id를 돌면서 re를 이용해 제재 조건을 만족하는 각각의 id를 리스트로 저장 (possible_id는 list의 list형식)

    - banned_id에서 '*'을 '\w'로 바꿔줌으로써 *에 모든 문자(숫자 포함)이 가능하도록 조건(정규식)을 생성

    - re.match를 사용해 처음부터 정규식과 만족하는 지 확인했으며, 길이 또한 같아야 하므로 길이도 확인

2. possible_id에서 itertools.product를 이용해 가능한 아이디의 모든 조합(dup_options)을 구함

3. dup_options 중에서 하나의 set 내에서 중복된 값과, 중복된 set가 있는 경우를 제거

    - 하나의 set 내에서 중복된 값은 list의 길이와 set의 길이 비교를 통해 제거

    - 중복된 set는 set를 정렬하여 중복된 값이 있는지 확인하여 제거

 

[코드]

import re
from itertools import product

def solution(user_id, banned_id): #{
    answer       = 0
    possible_id  = [] 

    # banned_id에 적합한 user_id를 possible_id에 저장
    for b_id in banned_id : #{
        re_b_id = b_id.replace('*', '\w')
        id_list = []

        for u_id in user_id : #{
            if re.match(re_b_id, u_id) and len(b_id) == len(u_id) : 
                id_list.append(u_id)  

        possible_id.append(id_list)
    #}

    # possible_id들의 조합
    dup_options = list(product(*possible_id))

    # id가 중복된 경우와 id 조합이 중복된 경우 제거
    options = []
    for op in dup_options : #{
        if len(op) == len(set(op)) and sorted(op) not in options: 
            options.append(sorted(op))
    #}

    return len(options)
#}

 

다 해 놓고, 바보같이 마지막에 전체 Option 리스트 중에서 중복 값(set)을 제거하는 방법이 생각나지 않아 다른 풀이 방법으로 한참 헤매다가 친구 찬스를 통해 중복값 제거 방법을 깨달았다.