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

출처: 프로그래머스 코딩 테스트 연습, [프로그래머스] 불량 사용자

풀이

1. 먼저 비트마스크를 사용하여 응모자 아이디 중 중복되지 않게 불량 사용자 수만큼 걸려낸다.
2. 걸려낸 사용자들과 불량 사용자가 모두 일치하는지 깊이우선탐색을 하여 확인한다. 이 때 모두 탐색하지 않고 True 가 될 때 바로 반환해줘야 시간초과나지 않는다.
3. 일치하는지 확인하는 메서드를 만든다. 만약 두 아이디의 길이가 다를 경우는 바로 False를 반환한다.

코드

def match(uid, bid):
    if len(uid) != len(bid): return False
    for v1, v2 in zip(uid, bid):
        if v2 == '*': continue
        if v1 != v2: return False
    return True

# 두 리스트 크기 같아야 됨
def match_list(uid_list, bid_list):
    if not uid_list and not bid_list:
        return True
    for i in range(len(uid_list)):
        for j in range(len(bid_list)):
            if match(uid_list[i], bid_list[j]):
                if match_list(uid_list[:i] + uid_list[i+1:], bid_list[:j] + bid_list[j+1:]):
                    return True
    return False

def solution(user_id, banned_id):
    answer = 0
    N = len(user_id)
    M = len(banned_id)
    for i in range(1, 1 << N):
        if bin(i)[2:].count('1') != M: continue
        uid_list = []
        for j in range(N):
            if i & (1 << j):
                uid_list.append(user_id[j])
        if match_list(uid_list, banned_id):
            answer += 1
    
    return answer

느낀점

문자열 매치하는 문제가 나오면 무조건 정규표현식으로 풀려는 생각을 버려야 겠다. 그냥 반복문으로 매칭하는 메서드를 만드는 것이 더 쉬운 길일 수 있다.