문제
문제 설명
개발팀 내에서 이벤트 개발을 담당하고 있는 무지는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 사용자라는 이름으로 목록을 만들어서 당첨 처리 시 제외하도록 이벤트 당첨자 담당자인 프로도 에게 전달하려고 합니다. 이 때 개인정보 보호을 위해 사용자 아이디 중 일부 문자를 '*' 문자로 가려서 전달했습니다. 가리고자 하는 문자 하나에 '*' 문자 하나를 사용하였고 아이디 당 최소 하나 이상의 '*' 문자를 사용하였습니다.
무지와 프로도는 불량 사용자 목록에 매핑된 응모자 아이디를 제재 아이디 라고 부르기로 하였습니다.
예를 들어, 이벤트에 응모한 전체 사용자 아이디 목록이 다음과 같다면
응모자 아이디 |
frodo |
fradi |
crodo |
abc123 |
frodoc |
다음과 같이 불량 사용자 아이디 목록이 전달된 경우,
불량 사용자 |
fr*d* |
abc1** |
불량 사용자에 매핑되어 당첨에서 제외되어야 야 할 제재 아이디 목록은 다음과 같이 두 가지 경우가 있을 수 있습니다.
제재 아이디 |
frodo |
abc123 |
제재 아이디 |
fradi |
abc123 |
이벤트 응모자 아이디 목록이 담긴 배열 user_id와 불량 사용자 아이디 목록이 담긴 배열 banned_id가 매개변수로 주어질 때, 당첨에서 제외되어야 할 제재 아이디 목록은 몇가지 경우의 수가 가능한 지 return 하도록 solution 함수를 완성해주세요.
제한사항
- user_id 배열의 크기는 1 이상 8 이하입니다.
- user_id 배열 각 원소들의 값은 길이가 1 이상 8 이하인 문자열입니다.
- 응모한 사용자 아이디들은 서로 중복되지 않습니다.
- 응모한 사용자 아이디는 알파벳 소문자와 숫자로만으로 구성되어 있습니다.
- banned_id 배열의 크기는 1 이상 user_id 배열의 크기 이하입니다.
- banned_id 배열 각 원소들의 값은 길이가 1 이상 8 이하인 문자열입니다.
- 불량 사용자 아이디는 알파벳 소문자와 숫자, 가리기 위한 문자 '*' 로만 이루어져 있습니다.
- 불량 사용자 아이디는 '*' 문자를 하나 이상 포함하고 있습니다.
- 불량 사용자 아이디 하나는 응모자 아이디 중 하나에 해당하고 같은 응모자 아이디가 중복해서 제재 아이디 목록에 들어가는 경우는 없습니다.
- 제재 아이디 목록들을 구했을 때 아이디들이 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리하여 하나로 세면 됩니다.
코드
import re #정규화 모듈
from itertools import permutations as pm #순열
def solution(user_id, banned_id):
banned_id = [x.replace("*", ".") for x in banned_id] #"."이 모든 문자와 매치되므로 replace
def check(id_, banned_id):
for i in range(len(id_)):
#제재 아이디가 아니거나 제재 아이디의 길이가 다르다면 pass
if not re.findall(banned_id[i], id_[i]) or len(id_[i]) != len(banned_id[i]):
return False
return True
stack = []
for id_ in pm(user_id, len(banned_id)): #제재 아이디 개수만큼 순열을 만든다
if check(id_, banned_id): #제재 아이디인지 아닌지 check
id_ = set(id_) #set()을 해주면 정렬이 된다
if id_ not in stack: #정렬된 id_가 아직 stack 안에 없다면 추가
stack.append(id_)
return len(stack)
진행 과정
예제 #1
user_id = ["frodo", "fradi", "crodo", "abc123", "frodoc"]
banned_id = ["fr*d*", "abc1**"]
1) id_ = ('frodo', 'fradi')
2) id_ = ('frodo', 'crodo')
3) id_ = ('frodo', 'abc123') #제재 아이디
4) id_ = {'abc123', 'frodo'} #set()을 함으로서 각 원소들이 일정한 위치에 배열됨
5) id_ = ('frodo', 'frodoc')
6) id_ = ('fradi', 'frodo')
7) id_ = ('fradi', 'crodo')
8) id_ = ('fradi', 'abc123') #제재 아이디
9) id_ = {'abc123', 'fradi'}
10) id_ = ('fradi', 'frodoc')
11) id_ = ('crodo', 'frodo')
12) id_ = ('crodo', 'fradi')
13) id_ = ('crodo', 'abc123')
14) id_ = ('crodo', 'frodoc')
15) id_ = ('abc123', 'frodo')
16) id_ = ('abc123', 'fradi')
17) id_ = ('abc123', 'crodo')
18) id_ = ('abc123', 'frodoc')
19) id_ = ('frodoc', 'frodo')
20) id_ = ('frodoc', 'fradi')
21) id_ = ('frodoc', 'crodo')
22) id_ = ('frodoc', 'abc123')
23) return 2
'Algorithm & Data Structure > Programmers' 카테고리의 다른 글
[Programmers]Python_스타 수열 (0) | 2020.12.24 |
---|---|
[Programmers]Python_야근 지수 (0) | 2020.12.23 |
[Programmers]Python_방문 길이 (0) | 2020.12.21 |
[Programmers]Python_멀리 뛰기 (0) | 2020.12.20 |
[Programmers]Python_거스름돈 (0) | 2020.12.19 |