[프로그래머스] 불량 사용자 / Python / 반례
문제주소 :programmers.co.kr/learn/courses/30/lessons/64064
코딩테스트 연습 - 불량 사용자
개발팀 내에서 이벤트 개발을 담당하고 있는 무지는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량
programmers.co.kr
<문제 설명>
문제 설명
개발팀 내에서 이벤트 개발을 담당하고 있는 무지는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 사용자라는 이름으로 목록을 만들어서 당첨 처리 시 제외하도록 이벤트 당첨자 담당자인 프로도 에게 전달하려고 합니다. 이 때 개인정보 보호을 위해 사용자 아이디 중 일부 문자를 '*' 문자로 가려서 전달했습니다. 가리고자 하는 문자 하나에 '*' 문자 하나를 사용하였고 아이디 당 최소 하나 이상의 '*' 문자를 사용하였습니다.
무지와 프로도는 불량 사용자 목록에 매핑된 응모자 아이디를 제재 아이디 라고 부르기로 하였습니다.
예를 들어, 이벤트에 응모한 전체 사용자 아이디 목록이 다음과 같다면
응모자 아이디| 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
문제 설명과 같습니다.
입출력 예 #2
다음과 같이 두 가지 경우가 있습니다.
제재 아이디| frodo |
| crodo |
| abc123 |
| frodo |
| crodo |
| frodoc |
입출력 예 #3
다음과 같이 세 가지 경우가 있습니다.
제재 아이디| frodo |
| crodo |
| abc123 |
| frodoc |
| fradi |
| crodo |
| abc123 |
| frodoc |
| fradi |
| frodo |
| abc123 |
| frodoc |
<풀이법>
▒ 한줄 개념: set ▒
점점 더 사소한 실수에 대해 반례를 찾는 경우가 늘어나는 것 같습니다. 안타깝네요..
이번 문제는 다양한 방식으로 풀 수 있는 문제입니다. 데이터의 양이라던가 조건들이 빡빡하지 않습니다.
DFS, 정규표현식이 가장 많이 사용된 방식인 것 같습니다.
문제 풀이 방식은 다음과 같습니다.
1. banned_id 별 매칭되는 user_id 찾고 저장.
'fr*d*': ['frodo', 'fradi'] 와 같이 해시맵으로 저장해도 되고, 단순 배열로 저장해도 됩니다. 어떤 방식이든 상관없이, 모든 banned_id에 대해 저장을 해줍니다.
2. 중복이 생기지 않도록 조합.
하나의 id배열에 대해서 중복이 있어서는 안되고, 그 id배열의 배열에도 중복이 있어서는 안됩니다. set()함수를 이용하면 좀 쉽게 해결할 수 있습니다.
<반례>
3번, 7번 테스트케이스가 자꾸 실패해서 몇 시간정도 걸린 것 같습니다. 문자열 비교 방식에서 오류가 발생한 것이었습니다.
user_id = ['fradi']
banned_id = ['frady']
answer = 0
<코드(Python)>
def solution(user_id, banned_id):
answer = []
candidates = [[]]
for b_id in banned_id:
new_candidates = []
for u_id in user_id:
if len(u_id) != len(b_id):
continue
check = True
for i in range(len(u_id)):
if b_id[i] != '*' and u_id[i] != b_id[i]:
check = False
break
if check:
for c in candidates:
if u_id not in c:
new_candidates.append(c+[u_id])
candidates = new_candidates
for c in candidates:
if set(c) not in answer:
answer.append(set(c))
return len(answer)
더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest