문제 요약
이벤트 응모자 아이디 목록 user_id와 불량 사용자 패턴 목록 banned_id가 주어진다.
불량 사용자 패턴에는 * 문자가 포함되어 있으며, *는 어떤 문자 하나와도 매칭될 수 있다.
각 불량 사용자 패턴에 응모자 아이디를 하나씩 매칭해야 한다.
단, 같은 응모자 아이디가 제재 아이디 목록에 중복으로 들어갈 수 없다.
최종 제재 아이디 목록은 순서와 관계없이 같은 아이디들로 구성되어 있으면 같은 경우로 본다.
가능한 제재 아이디 목록의 개수를 구해야 한다.
핵심 아이디어
이 문제는 다음 두 단계로 풀 수 있다.
- 각
banned_id패턴에 매칭 가능한user_id를 찾는다. - DFS로 패턴마다 사용자를 하나씩 선택하면서 가능한 제재 목록을 만든다.
최종 제재 목록은 순서가 달라도 같은 목록이면 하나로 처리해야 한다.
따라서 선택된 사용자들을 frozenset으로 만들어 결과 집합에 저장한다.
result.add(frozenset(selected))set은 mutable 자료형이라 다른 set 안에 넣을 수 없다.
반면 frozenset은 immutable 자료형이므로 set의 원소로 사용할 수 있다.
패턴 매칭 조건
응모자 아이디와 불량 사용자 패턴이 매칭되려면 다음 조건을 만족해야 한다.
- 길이가 같아야 한다.
- 각 위치의 문자가 같거나, 패턴 문자가
*여야 한다.
예를 들어 다음과 같은 패턴 비교를 생각할 수 있다.
user = "frodo"
ban = "fr*d*"각 위치를 비교하면 * 위치는 어떤 문자든 허용되므로 매칭된다.
풀이 과정
1. 매칭 함수 만들기
def is_match(user, banned):두 문자열의 길이가 다르면 매칭될 수 없다.
길이가 같다면 각 문자를 비교한다.
패턴 문자가 *이면 해당 위치는 통과한다.
2. DFS로 사용자 선택
banned_id를 앞에서부터 하나씩 확인한다.
현재 불량 사용자 패턴에 매칭되는 응모자 아이디 중 아직 선택하지 않은 아이디를 선택한다.
if user in selected:
continue이미 선택된 사용자는 다시 사용할 수 없다.
3. 최종 목록 저장
모든 불량 사용자 패턴에 대해 사용자를 선택했다면, 현재 선택된 사용자 목록을 결과에 저장한다.
result.add(frozenset(selected))이렇게 하면 순서만 다른 동일한 제재 목록은 자동으로 하나로 합쳐진다.
Python 코드
def solution(user_id, banned_id):
result = set()
def is_match(user, banned):
if len(user) != len(banned):
return False
for u, b in zip(user, banned):
if b == "*":
continue
if u != b:
return False
return True
def dfs(index, selected):
if index == len(banned_id):
result.add(frozenset(selected))
return
banned = banned_id[index]
for user in user_id:
if user in selected:
continue
if not is_match(user, banned):
continue
selected.add(user)
dfs(index + 1, selected)
selected.remove(user)
dfs(0, set())
return len(result)코드 설명
결과 저장 집합
result = set()가능한 제재 아이디 목록을 저장한다.
제재 목록은 순서와 관계없이 같은 구성이면 같은 경우로 처리해야 하므로, 최종 선택 목록을 frozenset으로 변환해서 저장한다.
패턴 매칭
def is_match(user, banned):응모자 아이디 user가 불량 사용자 패턴 banned와 매칭되는지 확인한다.
먼저 길이가 다르면 바로 False를 반환한다.
if len(user) != len(banned):
return False이후 각 문자를 비교한다.
if b == "*":
continue패턴 문자가 *이면 어떤 문자든 가능하므로 넘어간다.
*가 아닌 문자가 서로 다르면 매칭되지 않는다.
DFS 탐색
def dfs(index, selected):index는 현재 확인 중인 banned_id의 위치다.
selected는 지금까지 제재 아이디로 선택한 사용자 집합이다.
종료 조건
if index == len(banned_id):
result.add(frozenset(selected))
return모든 불량 사용자 패턴에 대해 매칭을 끝냈다면 하나의 제재 목록이 완성된 것이다.
중복 사용자 방지
if user in selected:
continue같은 응모자 아이디는 제재 목록에 한 번만 들어갈 수 있다.
이미 선택한 사용자는 건너뛴다.
백트래킹
selected.add(user)
dfs(index + 1, selected)
selected.remove(user)현재 사용자를 선택한 뒤 다음 패턴으로 넘어간다.
탐색이 끝나면 다시 제거해서 다른 선택지를 확인한다.
왜 frozenset을 사용할까?
최종 제재 아이디 목록은 순서와 관계없이 같은 목록이면 같은 경우다.
예를 들어 다음 두 목록은 같은 경우로 처리해야 한다.
["frodo", "abc123"]
["abc123", "frodo"]리스트나 튜플은 순서가 다르면 다른 값으로 비교된다.
하지만 집합은 순서를 고려하지 않는다.
다만 일반 set은 다른 set의 원소로 넣을 수 없기 때문에, immutable한 frozenset으로 바꿔 저장한다.
시간 복잡도
응모자 수를 U, 불량 사용자 패턴 수를 B, 아이디 길이를 L이라고 하자.
각 패턴마다 사용자를 선택하는 모든 경우를 탐색할 수 있다.
최악의 경우 시간 복잡도는 다음과 같이 볼 수 있다.
O(P(U, B) * L)P(U, B)는 U명 중 B명을 순서 있게 선택하는 경우의 수다.
하지만 제한에서 user_id의 길이는 최대 8이므로 완전 탐색으로 충분히 해결할 수 있다.
공간 복잡도
DFS 재귀 깊이는 banned_id의 길이에 비례한다.
결과 집합에는 가능한 제재 목록들이 저장된다.
O(가능한 제재 목록 수 * B)정리
이 문제는 패턴 매칭과 백트래킹을 함께 사용하는 문제다.
핵심은 다음과 같다.
*를 고려해 패턴과 사용자 아이디를 비교한다.- 불량 사용자 패턴마다 매칭 가능한 사용자를 DFS로 선택한다.
- 같은 사용자는 중복 선택하지 않는다.
- 최종 제재 목록은
frozenset으로 저장해 순서 중복을 제거한다.
입력 크기가 작기 때문에 전체 경우를 탐색하는 방식으로 깔끔하게 해결할 수 있다.
