[PROGRAMMERS] 2019 카카오 개발자 겨울 인턴십 : 불량 사용자 Python

프로그래머스의 불량 사용자 문제를 풀어보았다. 지난번에 풀다가 실패했던 링크 점수 이후로 정규화에 대해 공부해 보았기 때문에 이 문제를 봤을 때, 정규화로 풀어볼 수 있겠다는 생각이 들었다.

 

이 문제는 모든 아이디가 공개되어 있는 이벤트 응모자 아이디와 아이디가 일부분 '*'로 가려져 있는 불량사용자 아이디를 제공한다. 이 정보를 통해 이벤트 응모자 아이디 중 불량 아이디를 가려내고자 할 때, 불량 아이디로 가려내질 응모자 아이디의 경우의 수를 묻는다.

이렇게 두 정보가 제공됐을 때, 불량사용자로 인해 제재받는 경우의 수는 [frodo, abc123], [fradi, abc123] 이렇게 두 가지의 경우가 있다. 

추가적으로 고려해야 할 제약사항은 불량사용자 아이디는 무조건 하나의 응모자 아이디를 가리키고 있으며, 재재 대상 아이디가 만들어졌을 때, 중복되는 경우는 하나의 경우로 생각한다는 점이다

이 문제를 풀기위해서 나는 이 두 가지 사항을 고민했다.
1. 불량사용자를 골라내기 위해서 어떤 방법을 쓸 것인가 
2. 재재대상을 만들었을 때 경우의 수를 어떻게 구할 것인가. 

그리고 아래의 두 가지 방법으로 문제를 해결했다
1. re라이브러리를 이용한 정규화를 통해 불량 사용자 아이디와 유사한 응모자 아이디를 찾자
2. 찾은 아이디들을 통해 완전 탐색으로 경우의 수를 공개하자

먼저 코드를 보면

import re
def solution(user_id, banned_id):
    # 경우의 수를 구하는 함수
    def my_count(now):
        nonlocal cnt
        if now == N:
            tmp = sorted(check[:])
            if tmp not in my_answer:
                my_answer.append(tmp)
            return

        for str in candiates[now]:
            if str not in check:
                check.append(str)
                my_count(now+1)
                check.pop()
        else:
            return

    N = len(banned_id)
    candiates = [[] for _ in range(N)]
    # 정규화를 통한 불량사용자 찾기
    for i in range(N):
        ban_id = banned_id[i]
        key = ''
        for char in ban_id:
            key += '.' if char == '*' else char
        exp = re.compile(key)

        for id in user_id:
            if len(ban_id) == len(id) and exp.match(id):
                candiates[i].append(id)

    check = []
    my_answer = []
    my_count(0)

    return len(my_answer)

이렇게 된다.

정규화에 대한 자세한 부분은 내블로그에서 정리된 내용을 볼 수 있을 것이다.

다행히 이문제는 시간적인 측면을 보지 않기 때문에 완전 탐색 부분에서 시간을 많이 쓰는 함수를 사용했어도 통과했지만 시간 제약까지 있었더라면 더 까다로웠을 것 같다.

 

아직 실력이 많이 부족하여 어떤 문제를 풀어도 고민하고 구현하는 시간이 많이 걸리는 것 같지만 꾸준히 문제를 풀어본다. 

오늘도 하루 한개 알고리즘 파이팅!

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