문제

프로그래머스 불량 사용자

문제풀이

정규표현식 + dfs를 활용해야 하는 생각보다 까다로운 문제였다.

문제 풀이의 과정은 다음과 같다.

1. 주어진 문자열로 가능한 모든 케이스 생성
2. 가능한 제재 아이디 목록들 생성
   2-1. 나온 목록들 중 중복 제거

1. 모든 케이스 생성

문자열을 다루는 문제여서 2가지의 방법을 생각해보았다.

1. 정규표현식을 사용해 원하는 문자열을 만드는 방법
2. Trie 자료구조를 사용하는 방법

두 가지 방법 다 문제를 푸는데 지장은 없을 것 같아 정규표현식에 익숙해지고자 1번의 방법을 사용하였다.

모든 문자에 매칭할 수 있는 문자(.)와 원하는 패턴만 정확히 일치하기 위해 \\b 를 적절히 활용하여 모든 케이스를 생성하였다.

2. 가능한 제재 아이디 목록들 생성

처음에는 문제에서 주어진 banned_id 패턴이 다르면, 같은 값이 나와도 다른 케이스로 취급된다고 생각하여 갈피를 못 잡았었다.
하지만 문제를 다시 읽어보니 다음과 같은 제한사항이 있었다.

• 불량 사용자 아이디 하나는 응모자 아이디 중 하나에 해당하고 같은 응모자 아이디가 중복해서 제재 아이디 목록에 들어가는 경우는 없습니다.
• 제재 아이디 목록들을 구했을 때 아이디들이 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리하여 하나로 세면 됩니다.

즉, 별다른 고민없이 가능한 나올 수 있는 모든 제재 아이디 목록들을 생성하고, 중복된 것들을 제거하면 된다.

중복을 제거하기 위해 set과 frozenset을 활용하였다.

import re

def solution(user_id, banned_id):
    answer = 0
    
    # 1. make cases
    cases = []
    for b_id in banned_id:
        tmp = ""
        for c in b_id:
            if c != "*":
                tmp += c
            else:
                tmp += '.'
        
        tmp = '\\b' + tmp + '\\b'
        
        p = re.compile(tmp)
        
        case = []
        for user in user_id:
            word = p.search(user)
            if word:
                case.append(word.group())
    
        cases.append(case)

    # 2. count valid case
    N = len(cases)
    case_set = set()
    def search(k, res):
        if k == N:
            # 2-1. remove duplicate case
            case_set.add(frozenset(res))
        else:
            for c in cases[k]:
                if c not in res:
                    search(k+1, res + [c])
            
    search(0, [])

    answer = len(case_set)
    
    return answer