[Seop's의 코드풀이] 프로그래머스 불량사용자 - Python

이번에 풀어볼 문제는 프로그래머스에 있는 불량사용자 라는 문제입니다.

본 문제는 2019년 카카오 개발자 겨울 인턴십 코딩테스트로 나온 문제이기도 합니다.

문제는 다음과 같습니다.

 

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

프로그래머스

문제를 간략하게 요약 해 보면

 

응모자 아이디와 불량 사용자의 아이디가 주어진다.
뷸량 사용자의 아이디에는 일부 * 문자가 섞여 있다.
응모자 아이디 중에 불량 사용자일 가능성이 있는 아이디의 경우의 수를 구하자!

 

본 문제에서 가장 어려웟던 부분은

경우의 수를 구하는 것이었다.

필자는 여러가지 방법 중 조합을 통해 문제를 푸는 방법을 선택했다.

특히 itertools의 product 를 이용해 곱집합을 이용해서 풀었다.

 

위 방법은 

[1,2,3], [a,b]

두개의 리스트가 있다면 각 리스트에서 하나씩 뽑아서 조합을 만들어 준다.

테스트 케이스 3번에서 재재 아이디에 해당하는 것을 본다면

[['frodo', 'fradi'], ['frodo', 'crodo'], ['abc123', 'frodoc'], ['abc123', 'frodoc']]

이러한 형식이 됨으로 product를 이용한다면 유용 할 것이라 생각했다.

 

그 다음 정렬을 하고 중복되는 것들을 제거해주면

최종적으로 경우의 수가 나오게 된다.

 

코드에 대한 자세한 설명과 전체 코드는 다음과 같습니다.

질문과 피드백은 언제나 감사드립니다.

import itertools

def solution(user_id, banned_id):
    ban = dict()
    cnt = 0
    for b in banned_id :
        real_str = b
        cnt +=  1
        # 중복되는 값을 방지하기 위해 뒤에 숫자를 붙인다.(중복되는 경우)
        if b in ban :
            b += str(cnt)
        ban[b] = []

        # 별의 우치를 찾는 작업
        star = []
        for s in range(len(real_str)) :
            if real_str[s] == "*" : 
                star.append(s)
        
        for u in user_id :
            temp = 0
            buf = ""
            #  제재 아이디의 별의 위치에 맞도록 user id 를 수정 -> 비교 진행
            for i in star :
                if len(u) > i : 
                    buf += u[temp : i] + "*"
                    temp = i + 1
            if len(u) != len(buf) :
                buf += u[temp :]
            if real_str == buf :
                ban[b].append(u)
    
    ban_list = list(ban.values())
    #  곱집합을 재재 리스트에 있는 아이디 들로 곱집합을 구하는 과정
    #  -> 중복을 포함해서 모든 경우의 수를 구할 수 있다.
    ans_list = list(itertools.product(*ban_list))
    answer = set()
    for a in ans_list:
        # set 으로 중복을 제거했을때 항목 수가 줄어들었으면 pass 한다.
        if len(set(a)) == len(banned_id):
            #  정렬 후 문자열로 만들어 집어 넣어 중목을 방지한다.
            #  같은 것이 두개 들어가도 set로 설정되어 있기 때문에 중복되지 않는다.
            answer.add("".join(sorted(set(a))))

    return len(answer)