[프로그래머스] 불량 사용자, Python3

문제는 여기!

 

안녕하세요! 이번 포스팅에서는 2019 카카오 개발자 겨울 인턴십 문제였던 "불량 사용자"를 풀이해보겠습니다. 이 문제는 접근을 어떻게 할지 몰라서 결국 다른 분들의 풀이를 참고했습니다. 사실 봐도 좀 헷갈리는 부분이 있어서 이 기회에 정리할 겸 포스팅하게 되었습니다. 그럼 풀이 시작해보겠습니다!

 

제한사항 및 주의사항

user_id 배열의 크기는 1 이상 8 이하 입니다.

banned_id 배열의 크기는 1 이상 user_id 배열의 크기 이하 입니다.

user_id, banned_id의 각 원소들은 길이가 1 이상 8 이하인 문자열 입니다.

불량 사용자 아이디는 '*' 문자를 하나 이상 포함하고 있습니다.

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

제재 아이디 목록을 구했을 때, 아이디들이 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 간주합니다.

나의 풀이 방법

user_id와 banned_id의 크기가 크지 않습니다. 저는 이 문제를 완전탐색으로 풀이해보겠습니다.

문제에서 하나의 불량 사용자 아이디는 하나의 응모자 아이디에 해당합니다. 이 말은 banned_id에 원소 값이 중복될 수 있지만, 어쨌든 user_id의 목록 중에서 하나에 매치됩니다.

permutation 모듈을 이용해보겠습니다. permutation을 이용해 user_id 목록을 banned_id의 크기만큼 순열로 구성된 user_id 리스트를 뽑아보겠습니다.

예를 들어 user_id가 [1, 2, 3], banned_id의 크기가 2라면, 반환되는 리스트는 [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]가 반환될 것입니다. 이 말은 banned_id 크기에 맞는 모든 경우의 수 들을 user_id 배열에서 뽑아온다는 의미입니다. 그래서 제가 앞에서 완전탐색으로 풀이했다고 말씀드린거구요!

그 다음 리스트안에 있는 원소들(순열들, user_id P len(banned_id) 의 결과)을 하나씩 검사해줍니다. 검사하는 로직은 is_match라고 따로 분리했습니다.

검사하는 과정은, 각 검사하려는 순열들의 길이와 banned_id의 길이는 동일하기 때문에 같이 반복문을 통해 인덱스를 돌려 검사합니다. True 혹은 False를 반환하는데요, 일단 len(user_id[i]) != len(banned_id[i])일 경우는 당연히 False를 반환해야 합니다. len(user_id[i]) == len(banned_id[i])라면 해당 원소들을 하나씩 반복문을 통해 검사합니다. 만약 banned_id의 글자 하나가 '*' 라면 continue, user_id의 글자와 banned_id 글자가 일치하지 않다면 False를 반환합니다.

이렇게 해서 True가 반환된 user_id 순열은 set으로 형변환 합니다. 그 이유는 앞의 문제에서 제재 아이디 목록들을 구했을 때 아이디들이 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리하여 하나로 세면 됩니다 라는 조건이 있었기에, 내용의 중복제거를 위해 set으로 형변환했습니다. 그리고 배열에 담아주어 마지막에 이 set들을 담은 배열의 길이를 리턴해주면 제재 아이디 목록의 경우의 수가 나옵니다.

언제나 피드백은 환영해요!

from itertools import permutations


def is_match(user_set, banned_set):
    for i in range(len(user_set)):
        if len(user_set[i]) != len(banned_set[i]):
            return False
        for j in range(len(user_set[i])):
            if banned_set[i][j] == '*':
                continue
            if banned_set[i][j] != user_set[i][j]:
                return False
    return True


def solution(user_id, banned_id):
    answer = []
    for com_set in permutations(user_id, len(banned_id)):
        if is_match(com_set, banned_id):
            com_set = set(com_set)
            if com_set not in answer:
                answer.append(com_set)

    return len(answer)