프로그래머스

프로그래머스 불량 사용자 풀이: 비트마스크 DFS 매칭

2026년 9월 14일

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

문제: 불량 사용자
출처: 프로그래머스, 2019 카카오 개발자 겨울 인턴십
자체 판단 난이도: Level 3

불량 사용자 패턴과 매칭되는 사용자 후보를 찾은 뒤, 한 사용자를 두 번 선택하지 않는 모든 배정을 탐색해야 한다. 같은 사용자 집합을 선택한 결과는 순서와 관계없이 하나로 세야 하므로 DFS, 비트마스크, 중복 제거를 함께 사용해야 해 Level 3으로 판단했다.

1. 문제 요약

user_id에는 응모자 아이디가, banned_id에는 일부 문자가 *로 가려진 불량 사용자 패턴이 주어진다. 각 불량 패턴에 서로 다른 사용자 아이디를 하나씩 매칭해 만들 수 있는 제재 아이디 목록의 경우의 수를 반환한다.

매칭 규칙은 다음과 같다.

아이디 길이가 같아야 한다.
banned_id의 *는 해당 위치의 문자 하나와 매칭된다.
*가 아닌 문자는 사용자 아이디의 같은 위치 문자와 같아야 한다.
하나의 사용자 아이디는 한 번만 선택할 수 있다.
선택된 아이디의 순서가 달라도 같은 집합이면 하나의 경우로 센다.

사용자 수는 최대 8명이고 불량 패턴 수도 사용자 수 이하이므로, 모든 후보 조합을 DFS로 확인할 수 있다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

후보 생성과 검증

먼저 각 banned_id 패턴에 대해 매칭 가능한 사용자 인덱스 목록을 만든다. 패턴과 사용자 아이디의 길이가 다르면 즉시 제외하고, 같은 위치에서 패턴 문자가 *가 아니면서 사용자 문자와 다르면 제외한다.

그 후 banned_id의 순서대로 DFS를 진행한다. 현재 패턴의 후보 사용자 중 아직 사용하지 않은 사람을 선택하고 다음 패턴으로 이동한다. 모든 패턴에 사용자를 배정하면 지금까지 선택한 사용자 집합을 결과에 저장한다.

비트마스크로 방문 기록 관리

사용자 인덱스 i가 선택되었는지는 정수의 i번째 비트로 표현한다.

선택 여부 확인: used & (1 << i)
사용자 선택: used | (1 << i)

예를 들어 사용자 0번과 2번을 선택했다면 비트마스크는 0101이다. 이 정수는 해시 가능한 값이므로 모든 패턴을 매칭한 뒤 set에 넣으면 선택 순서가 다른 동일한 사용자 조합이 자동으로 하나로 합쳐진다.

탐색 경로가 아니라 선택된 사용자 집합을 세는 이유

불량 패턴의 순서에 따라 DFS가 같은 사용자 집합을 여러 번 만들 수 있다. 예를 들어 ["*rodo", "*rodo"]가 있고 frodo, crodo가 모두 매칭된다면 첫 패턴에 frodo를 선택하는 경우와 crodo를 선택하는 경우가 탐색되지만, 최종 제재 아이디 집합은 둘 다 {frodo, crodo}로 같다.

따라서 DFS 경로 자체의 개수가 아니라, 모든 매칭이 끝났을 때의 비트마스크 개수를 세어야 정답의 의미인 사용자 집합의 경우의 수를 정확히 계산할 수 있다.

상태 전이와 경계 처리

DFS 상태는 (pattern_index, used_mask)다.

현재 불량 패턴에 대해 후보 사용자 목록을 확인한다.
used_mask에 없는 후보만 선택한다.
해당 사용자 비트를 켜고 다음 패턴으로 재귀 호출한다.
모든 패턴을 처리하면 used_mask를 결과 집합에 추가한다.

모든 패턴을 처리했다는 것은 len(banned_id)명의 서로 다른 사용자를 성공적으로 선택했다는 뜻이다. 문제에서 가능한 경로가 없는 경우는 주어지지 않지만, 어떤 DFS 분기가 막히면 그 분기만 종료하고 이전 상태로 돌아가 다른 후보를 확인한다.

오답 접근과 반례

각 패턴에서 사전순으로 첫 번째 매칭 사용자만 선택하면 다른 유효한 조합을 놓칠 수 있다.

user_id = ["frodo", "fradi", "crodo", "abc123", "frodoc"]
banned_id = ["*rodo", "*rodo", ""]

*rodo는 frodo와 crodo에 모두 매칭된다. 첫 패턴에서 frodo만 고정하면 crodo를 선택하는 경우를 놓칠 수 있다. 가능한 후보를 모두 DFS로 탐색해야 한다.

반대로 DFS 경로의 개수만 반환하면 같은 집합을 중복해서 세게 된다. 위 예제에서 두 *rodo 패턴에 frodo, crodo를 서로 다른 순서로 배정하는 경로는 여러 개지만 선택된 사용자 집합은 동일하므로 비트마스크 set으로 중복을 제거해야 한다.

시간·공간 복잡도

사용자 수를 U, 불량 패턴 수를 B, 아이디 최대 길이를 L이라고 하자. 후보 매칭 생성에는 O(BUL) 시간이 필요하다. DFS는 최악의 경우 사용자 배정 순열을 탐색하지만 U <= 8로 제한되어 있으며, 각 결과 마스크를 집합에 저장한다.

후보 목록과 DFS 결과 집합을 저장하는 공간은 O(BU + R)다. R은 발견한 사용자 집합의 수다.

3. 문제 해결 코드 (Python)

def solution(user_id, banned_id):
    candidates = []

    for pattern in banned_id:
        matches = []

        for user_index, user in enumerate(user_id):
            if len(user) != len(pattern):
                continue

            if all(
                pattern_char == "*" or pattern_char == user_char
                for pattern_char, user_char in zip(pattern, user)
            ):
                matches.append(user_index)

        candidates.append(matches)

    cases = set()

    def dfs(pattern_index, used):
        if pattern_index == len(candidates):
            cases.add(used)
            return

        for user_index in candidates[pattern_index]:
            bit = 1 << user_index
            if used & bit:
                continue

            dfs(pattern_index + 1, used | bit)

    dfs(0, 0)
    return len(cases)

candidates를 먼저 만들어 DFS 안에서 문자열을 반복 비교하지 않도록 했다. used는 선택된 사용자 집합을 나타내므로, 재귀가 끝날 때 이를 그대로 cases에 넣어 순서가 다른 배정을 하나로 합친다.

복사해 실행할 테스트

아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 패턴 매칭과 조합 중복 제거를 확인할 수 있다.

assert solution(
    ["frodo", "fradi", "crodo", "abc123", "frodoc"],
    ["fr*d*", "abc1**"],
) == 2
assert solution(
    ["frodo", "fradi", "crodo", "abc123", "frodoc"],
    ["*rodo", "*rodo", "******"],
) == 2

4. 공식 예제와 추가 검증

공식 예제와 동일 패턴 반복, 모든 후보가 같은 길이로 매칭되는 경우를 Python 코드로 실행했다.

공식 예제

입력	기대 출력	확인 결과
`user_id = ["frodo", "fradi", "crodo", "abc123", "frodoc"]`, `banned_id = ["frd", "abc1"]`	2	통과
같은 사용자 목록, `banned_id = ["rodo", "rodo", ""]`	2	통과
같은 사용자 목록, `banned_id = ["frd", "*rodo", "", ""]`	3	통과

추가 검증 1: 같은 패턴 두 개와 세 사용자

입력: user_id = ["abc", "abd", "abe"], banned_id = ["ab*", "ab*"]
기대 출력: 3
확인 결과: 통과
검증 목적: 두 패턴에 서로 다른 두 사용자를 선택하는 조합을 중복 없이 세는지 확인

5. 다른 풀이 방식 검색 및 비교

프로그래머스 공식 문제는 와일드카드 패턴과 중복 없는 제재 아이디 집합의 경우의 수를 정의한다.
vkdldjvkdnj의 DFS·비트마스크 풀이는 사용자 매칭 상태를 비트마스크로 기록하고 최종 조합의 중복을 제거하는 접근을 설명한다.

정규표현식으로 *를 한 글자 와일드카드로 바꿔 매칭할 수도 있지만, 아이디 길이가 짧고 문자 위치가 고정되어 있으므로 이 글에서는 직접 문자를 비교했다. 방문 배열을 사용하는 DFS도 같은 결과를 만들 수 있지만, 비트마스크를 결과 집합의 키로 바로 사용할 수 있어 선택 순서와 무관한 조합 중복 제거가 간단하다.

마무리

불량 사용자는 패턴별 매칭 후보를 먼저 만들고, 사용자 중복을 막으며 모든 배정을 탐색하는 백트래킹 문제다. 사용자 선택 상태를 비트마스크로 표현하면 방문 확인과 조합 식별을 하나의 정수로 처리할 수 있고, 최종 마스크를 집합에 저장해 순서가 다른 동일 조합을 정확히 하나로 계산할 수 있다.