◾ 불량 사용자 : 프로그래머스 LEVEL 3
문제
개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 사용자라는 이름으로 목록을 만들어서 당첨 처리 시 제외하도록 이벤트 당첨자 담당자인 "프로도" 에게 전달하려고 합니다. 이 때 개인정보 보호을 위해 사용자 아이디 중 일부 문자를 '*' 문자로 가려서 전달했습니다. 가리고자 하는 문자 하나에 '*' 문자 하나를 사용하였고 아이디 당 최소 하나 이상의 '*' 문자를 사용하였습니다.
"무지"와 "프로도"는 불량 사용자 목록에 매핑된 응모자 아이디를 제재 아이디 라고 부르기로 하였습니다.
예를 들어, 이벤트에 응모한 전체 사용자 아이디 목록이 다음과 같다면
| 응모자 아이디 |
|---|
| 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 이하인 문자열입니다.
- 불량 사용자 아이디는 알파벳 소문자와 숫자, 가리기 위한 문자 '*' 로만 이루어져 있습니다.
- 불량 사용자 아이디는 '*' 문자를 하나 이상 포함하고 있습니다.
- 불량 사용자 아이디 하나는 응모자 아이디 중 하나에 해당하고 같은 응모자 아이디가 중복해서 제재 아이디 목록에 들어가는 경우는 없습니다.
- 제재 아이디 목록들을 구했을 때 아이디들이 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리하여 하나로 세면 됩니다.
출력
- 당첨에서 제외되어야 할 제재 아이디 목록 경우의 수
입출력 예
| user_id | banned_id | result |
|---|---|---|
| ["frodo", "fradi", "crodo", "abc123", "frodoc"] | ["fr*d*", "abc1**"] | 2 |
| ["frodo", "fradi", "crodo", "abc123", "frodoc"] | ["*rodo", "*rodo", "**"] | 2 |
| ["frodo", "fradi", "crodo", "abc123", "frodoc"] | ["fr*d*", "*rodo", "******", "******"] | 3 |
◾ 풀이
1. 해설
- 모든 경우의 수를 확인하여 가능한 제재 아이디 목록 개수를 확인한다.
- banned_id에 대해 user_id가 가능한지 확인
- 완성된 제재 아이디 목록이 새로운 경우 (제재 아이디 목록 개수 +1)
2. 프로그램
- user_id를 banned_id의 개수만큼 뽑아낸다.(permutations 활용)
- 매치된 아이디와 banned_id를 비교하여 가능한지 확인
- 완성된 제재 아이디 목록이 가능하면 (제재 아이디 목록 개수 + 1)
# 코드
from itertools import permutations
def solution(user_id, banned_id):
answer = 0
ban_size = len(banned_id)
include_dict = {}
# permutations를 이용해 가능한 조합 모두 확인
for p_user in permutations(user_id, ban_size):
new_ban = []
for i in range(ban_size):
# 길이가 다른 경우 제재 아이디가 아니므로 종료
if len(banned_id[i]) != len(p_user[i]):
break
else:
flag = True
# p_user[i]와 banned_id[i] 비교
# 알맞지 않은 부분이 있는 경우 종료
for j in range(len(banned_id[i])):
if banned_id[i][j] != '*' and p_user[i][j] != banned_id[i][j]:
flag = False
break
# flag가 True인 경우 추가
if flag:
new_ban.append(p_user[i])
# 제재 아이디 목록이 banned_id 사이즈와 같은 경우
# 새로운 조합인지 확인
if len(new_ban) != ban_size:
continue
else:
new_ban = tuple(sorted(new_ban))
# 새로운 조합인 경우 개수 +1
if new_ban not in include_dict:
include_dict[new_ban] = True
answer += 1
return answer
후라이드 치킨