불량 사용자

문제 보기 · Level 3 · 2019 카카오 개발자 겨울 인턴십 · 정답률 53% · 푼 사람 13,351명 (2026-09-30 기준)¹

문제

응모자 아이디 목록과, 일부 글자를 *로 가린 불량 사용자 아이디 목록이 주어진다. *는 글자 하나를 가린다. 불량 사용자 아이디마다 서로 다른 응모자 아이디를 하나씩 짝지을 때 나올 수 있는 제재 아이디 묶음의 가짓수를 돌려준다. 순서만 다른 묶음은 하나로 센다.

응모자 1~8명, 아이디 1~8글자
불량 사용자 아이디 수 ≤ 응모자 수

풀이

막히면 한 단계씩 펼친다.

필요한 개념

재귀와 백트래킹: 불량 아이디마다 응모자를 하나씩 골라 짝짓고, 안 되면 되돌린다.
딕셔너리와 집합: 순서만 다른 묶음을 하나로 세려고 묶음을 집합으로 모은다.
순열과 조합: 백트래킹은 순서 있는 배정(순열)을 만들지만, 답은 순서를 지운 묶음의 수다. 묶음마다 나오는 배정 수가 다를 수 있어서 \(k!\)(불량 아이디 수 \(k\)의 계승)로 나눌 수 없다.

1단계 · 작은 예로 손으로 풀기

응모자 [frodo, fradi, crodo], 불량 [frd, *rodo]

frd에 맞는 응모자: frodo, fradi (글자 수가 같고, *가 아닌 자리의 글자가 같다)
*rodo에 맞는 응모자: frodo, crodo
서로 다르게 고르는 방법: (frodo, crodo), (fradi, frodo), (fradi, crodo)
묶음(순서 무시): {frodo, crodo}, {fradi, frodo}, {fradi, crodo} → 3가지

(frodo, frodo)는 같은 사람을 두 번 쓰니 안 된다.

2단계 · 가장 단순한 방법과 그 속도

응모자가 최대 8명이라, 불량 아이디 k개에 응모자를 순서대로 배정하는 모든 경우는 많아야 8! = 40,320가지다. 모두 해 봐도 된다.

3단계 · 핵심 아이디어

맞는지 확인: 두 아이디의 길이가 같고, 자리마다 불량 쪽 글자가 *이거나 두 글자가 같으면 맞는다.
백트래킹: 불량 아이디를 0번부터 차례로 보며, 아직 안 쓴 응모자 중 맞는 사람을 골라 다음 불량 아이디로 간다. 끝까지 가면 고른 사람들의 집합(frozenset)을 결과 집합에 넣는다.
순서 무시: 같은 사람들을 다른 순서로 고른 결과는 같은 frozenset이라 결과 집합에 한 번만 들어간다. 답은 결과 집합의 크기다. 고른 사람이 같은 배정끼리 한 동치류로 묶이고, frozenset은 동치류마다 하나뿐인 이름표다.

4단계 · 코드 흐름

맞는지 확인하는 함수를 만든다.
go(i, 쓴 사람들): i가 불량 수와 같으면 쓴 사람들을 결과에 넣는다. 아니면 안 쓴 응모자 중 i번 불량과 맞는 사람마다 넣고 go(i + 1), 빼기.
결과 집합의 크기를 돌려준다.

5단계 · 파이썬 코드

def solution(user_id, banned_id):
    def match(user, ban):
        return len(user) == len(ban) and all(b == "*" or b == u for u, b in zip(user, ban))

    results = set()
    used = []

    def go(i):
        if i == len(banned_id):
            results.add(frozenset(used))      # 순서 없는 묶음으로 저장
            return
        for u in user_id:
            if u not in used and match(u, banned_id[i]):
                used.append(u)
                go(i + 1)
                used.pop()                    # 되돌리기

    go(0)
    return len(results)

all(… for u, b in zip(user, ban)): 자리마다 조건이 모두 맞는지 본다.
frozenset(used): 바꿀 수 없는 집합이다. 보통 집합(set)은 다른 집합의 원소가 될 수 없어서 이것을 쓴다.

6단계 · 실행 추적

응모자 [frodo, fradi, crodo, abc123, frodoc], 불량 [frd, abc1**]

go(0): frd	go(1): abc1**	결과에 넣는 묶음
frodo	abc123	{frodo, abc123}
fradi	abc123	{fradi, abc123}

답은 2다.

7단계 · 복잡도와 흔한 실수

배정 경우는 많아야 8! = 40,320가지이고, 경우마다 맞는지 확인에 8글자 × 8번이다.

순서만 다른 묶음을 따로 센다. 예시 2처럼 불량 아이디가 같은 모양(*rodo, *rodo)이면 같은 두 사람을 순서만 바꿔 두 번 만든다.
길이 확인을 빼먹어 frodoc이 fr*d*에 맞는다고 본다.
같은 응모자를 두 불량 아이디에 쓴다.

검증: 문제의 예시 3개를 통과했고, 무작위 입력 2,000개에서 itertools.permutations로 모든 배정을 만드는 방법과 결과가 같았다 — 17_pg64064_p1.py

프로그래머스 스쿨, “불량 사용자” (https://school.programmers.co.kr/learn/courses/30/lessons/64064), 2026-09-30 조회. ↩