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

아이디어 도출 방법

user_id가 최대 8개 임으로 조합을 구성해도 8 * 7 * 6이 최대로 나온다. 따라서 permutations을 사용해 나올 수 있는 모든 순열을 구성한다.

 

생성된 조합에서 해당 아이디가 banned_id에 대응되는지 확인한 후 중복을 확인한 후 list에 넣어주면 된다.

 

중복을 확인하기(순서가 상관없기 때문임) 위해서 순열에서 만든 후보 리스트를 set으로 변환하면 리스트가 정렬된 형식으로 나오게 된다. 예를 들면 (c, d, a) -> set(a, b, c)의 형식이 된다. 따라서 후보 값들의 중복을 제거할 수 있다.

최종 결과

from itertools import permutations

def validate(user, ban):
    if len(user) != len(ban):
        return False
    else:
        for i, j in zip(user, ban):
            if j == '*':
                continue
            if i != j:
                return False
        return True


def solution(user_ids, banned_id):
    answer = []
    
    for i in permutations(user_ids, len(banned_id)):
        is_banned = True

        for user_id, ban_id in zip(i, banned_id):
            if not validate(user_id, ban_id):
                is_banned = False

        if is_banned:
            if not set(i) in answer:
                answer.append(set(i))


    return len(answer)


if __name__ == "__main__":
    user_id = 	["frodo", "fradi", "crodo", "abc123", "frodoc"]
    ban_id = ["*rodo", "*rodo", "******"]

    print(solution(user_id, ban_id) == 2)

 

후기

처음에는 ban_id에 적합한 후보키들을 찾아서 dfs형식으로 풀어나갔다. 하지만 문제가 발생했다. 중복을 제거하려면 코드가 엉성해진다는 것이었다. 따라서 사람들은 어떻게 해결했나 참고했더니 아래와 같은 깔끔한 풀이가 존재했다. 위 풀이도 아래의 풀이와 유사한데 이는 아래의 코드를 참고해 구현했기 때문이다. 

https://bladejun.tistory.com/49