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

문제 출처: 프로그래머스

프로그래머스

 

문제 설명

🔎개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다.
이런 응모자들을 따로 모아 "불량 사용자"라는 이름으로 목록을 만들어서 당첨 처리 시 제외하도록 이벤트 당첨자 담당자인 "프로도" 에게 전달하려고 합니다.
이 때 개인정보 보호을 위해 사용자 아이디 중 일부 문자를 '*' 문자로 가려서 전달했습니다.
가리고자 하는 문자 하나에 '*' 문자 하나를 사용하였고 아이디 당 최소 하나 이상의 '*' 문자를 사용하였습니다.
"무지"와 "프로도"는 불량 사용자 목록에 매핑된 응모자 아이디를 "제재 아이디" 라고 부르기로 하였습니다.

출처: 프로그래머스

문자열 처리 문제는 언제나 귀찮음을 동반한다.

그리고 해당 문제는 브루트포스가 아닌 방법으로 접근하면 상당히 어렵게 느껴졌다.

제한사항을 잘 읽어보고 바로 브루트포스를 떠올렸다면 상당한 침착한 실력자임이 분명하다..

 

<정답 코드>

from itertools import permutations
import re

def solution(user_id, banned_id):
    n = len(banned_id)
    answer = set()
    banned_id = [i.replace('*', '.') for i in banned_id]
    
    for per in permutations(user_id, n):
        tmp = list(per)
        for i in range(n):
            if not(re.match(banned_id[i], tmp[i]) and len(tmp[i]) == len(banned_id[i])):
                break
        else:
            tmp.sort()
            answer.add(tuple(tmp))

    return len(answer)

개인적으로 permutations, combinations를 사용하지 않는 것을 선호하지 않는다.

옛날에 처음 itertools를 알게 됐을 때 신나게 사용하다가 항상 시간초과를 먹었기 때문에 친하지 않다..

 

하지만 이 문제에서는 배열의 길이가 최대 8이므로 permutation을 이용해도 시간을 많이 잡아먹지 않아 결국은 사용하게 됐다.

 

접근은 아래와 같다.

1. user_id에서 banned_id 길이 만큼의 아이디를 순열로 추출한다.
   • 순열로 추출하는 이유: user_id 배열의 순서와 상관없이 banned_id가 구성되었기 때문
2. 추출된 순열 전체를 탐색하면서 banned_id 전체와 매칭되는지 확인한다.
   • 매칭되는가는 re 모듈을 활용해서 진행한다.
   • re.match 함수는 '.'이 입력된 자리에는 어떤 문자든 대체 가능하기 때문에, 우선적으로 banned_id의 원소를 구성하는 '*'을 '.'로 대체하는 작업을 진행하고 순회한 것이다.
   • 또한, match는 길이와 상관없이 "해당 문자들로 시작한다면 True"이기 때문에 길이 검사를 따로 해줘야한다.

처음에는 match도 직접 구현하려하고, permutation이 아닌 match되는 문자들을 추출한 다음 조합하려했으나, 결국은 banned_id의 길이만큼 반복해야한다는 것이 permutation과 같은 복잡도를 가져 그냥 가져다 쓰게 되었다.

 

파이썬이라는 언어가 가진 훌륭한 특징인 라이브러리들은 문제 해결에 큰 도움을 줄 수 있지만, 어떻게 동작하는지 정확히 파악하지 않고 쓰면 오히려 문제 해결에 방해가 될 수 있는 것 같다.

 

항상 유의해서 사용하도록 하자.