[Programmers] - 불량 사용자 (2019 카카오 개발자 겨울 인턴십) with Python

📎 간략한 문제 정리

• 입력된 사용자 목록에서 불량 사용자 목록에 등록된 아이디를 제거합니다. 불량 사용자 목록에 있는 아이디는 정확한 아이디가 아니라 *를 사용한 아이디로 *에는 어떠한 문자가 들어가든 다른 문자가 매칭되면 제거합니다. 이렇게 제거 가능한 아이디 조합의 종류를 찾는 문제입니다.

📈 문제 분석

• 문제가 어렵지 않아 보이지만 보기보다 난이도가 있는 문제입니다. 계속 가능성을 제외하는 좋은 로직을 생각하는 함정에 빠지면 구현에서 문제가 생깁니다. 한번에 모든 문제를 해결하려는 로직을 구현할 수 있다면 이상적이지만 언제나 완전 탐색의 가능성을 배제하면 안됩니다.

🙋‍♂️ 내가 처음 생각한 해결 방법

• 수학적으로 계산하려고 했습니다. 가능성이 있는 모든 경우를 찾아 교집합 부분을 제거하려고 했는데 이 방법은 불량 사용자 아이디가 2개 일때는 쉽게 가능하지만 그 개수가 늘어나면 문제가 발생합니다. 수학적으로 교집합의 가능성이 매우 늘어나 모든 것을 계산하기 힘들기 때문입니다.

💻 풀이한 코드

def is_check(criterion, target):
    import re
    if len(criterion) != len(target):
        return False
    p = re.compile(criterion.replace("*", "."))
    if p.match(target):
        return True
    else:
        return False

def check_ids(user_id_list, banned_id_list):
    for i in range(len(banned_id_list)):
        if not is_check(banned_id_list[i], user_id_list[i]):
            return False
    return True

def solution(user_id, banned_id):
    from itertools import permutations
    cache = set()
    test_cases = permutations(user_id, len(banned_id))
    for test_case in test_cases:
        if check_ids(test_case, banned_id):
            cache.add(tuple(sorted(test_case)))
    return len(cache)

📝 해결 과정에서 만난 문제, 고민들

• 예시를 한가지만 보고 문제 해결법을 생각하다보면 문제가 생기기 쉽습니다. 로직을 구현할 때 너무 단편적인 로직만 생각하는 것이 아니라 다른 예시에도 적용되는지 볼 필요가 있습니다.

• 정규표현식을 구현할 때 문제가 있었습니다.

  "a*c" <-> "abc" # 매칭
  "a*c" <-> "bcc" # 매칭 안됨
  "a*c" <-> "abcd" # 매칭됨

  정규표현식을 사용하면 기준 문자열의 길이까지 매칭되면 문자열이 더 길어도 참을 반환하는 문제가 있었습니다. 이것을 해결하려고 정규표현식의 문법을 더 학습했지만 생각해보면 조건에서 길이가 다르면 절대 성립이 안되기때문에 앞선 조건으로 처리 가능했습니다.

• 문제의 조건 범위를 무시하면 안됩니다. 문제를 보면 달려들어 효율적인 방법을 생각하는 습관이 있는데 이렇게 되면 오히려 해결법에 문제가 발생합니다. 범위는 다음과 같은 힌트가 될 수 있습니다.

  100억 같이 매우 높은 숫자 -> 이분 탐색 가능성 생각

  10만 -> 쉽게 생각하면 O(N^2)이지만 효율적인 연산으로 O(NlogN)으로 처리해야됨

  10,000 이하의 매우 작은 수 -> 완전 탐색을 고려

  50 이하의 매우 작은 수 -> 순열, 조합 등을 사용한 완전 탐색을 고려

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