반응형
2019 카카오 개발자 겨울 인턴십 문제입니다.
문제풀이
1. 정규표현식에서 '.'은 모든 문자 1개를 의미합니다. 따라서 banned_id의 모든 '*'을 '.'으로 바꾼 후 이를 컴파일러로 사용합니다.
2. user_id의 아이디 하나 u가 banned_id의 하나 b에 해당되기 위해서는 b로 만든 컴파일러에 u가 걸리고, b와 u의 길이가 같아야합니다. 저는 정규표현식의 match를 활용하였는데, match를 활용하면 'a.b'로 만든 컴파일러에 'aabb' 또한 매칭되므로 두번째 조건이 필요합니다.
3. 2 과정을 통해 모든 b에 해당하는 u의 리스트를 만듭니다.
| user_id | banned_id |
| ["frodo", "fradi", "crodo", "abc123", "frodoc"] | ["fr*d*", "abc1**"] |
이 예를 사용하면 3의 결과는 다음과 같습니다.
{0: ['frodo', 'fradi'], 1: ['abc123']}
여기서 key값인 숫자는 b의 index입니다.
4. 3의 결과인 dictionary를 dfs 하여 최종 결과를 만들어냅니다.
*말로는 설명이 잘 안되어 아래 코드에서 자세히 다시 설명하겠습니다.
Python Code
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
import re
def solution(user_id, banned_id):
# 가능한 제재id
global answer
answer = []
# key : banned_id의 id의 index, value : 아래의 checked
candidate = {}
for i, b in enumerate(banned_id):
# re.sub를 활용하여 b의 모든 *을 .으로 변환
checker = re.compile(re.sub('\*','.',b))
# banned_id 중 하나인 b에 매칭되는 user_id
checked = []
for u in user_id:
# match가 안되면 결과가 None으로 두번째 조건 만족x
if len(u) == len(b) and checker.match(u):
checked.append(u)
candidate[i] = checked
# candidate를 활용하여 dfs
for x in candidate[0]:
dfs([x],candidate,len(banned_id))
return len(answer)
'''
selected는 list로 selected[i]는 candidate[i]의 원소 중 하나. 즉 i번째 banned_id에 매칭되는 user_id 중 하나.
n은 banned_id의 길이.
dfs의 탈출 조건은 selected에 들어있는 원소의 수가 n이 되는 것이다.
'''
def dfs(selected,candidate, n):
# 탈출조건
if len(selected) == n:
global answer
# 중복을 제거하기 위해 selected를 정렬한 후 비교
tmp = sorted(selected)
if tmp not in answer:
answer.append(tmp)
return ;
'''
<selected의 원소 수가 n이 아닌 경우.>
selected의 원소 수는 다음 banned_id의 index를 의미한다.
ex) selected에 한개가 들어있으면 banned_id[1](banned_id의 두번째 요소)에 매칭되는 user_id의 집합인
candidate[1]의 원소 중 하나를 selected에 넣는다.
'''
for x in candidate[len(selected)]:
if x not in selected:
dfs(selected+[x],candidate,n)
|
cs |
문제링크
코딩테스트 연습 - 불량 사용자
개발팀 내에서 이벤트 개발을 담당하고 있는 무지는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량
programmers.co.kr
반응형
'알고리즘 > 프로그래머스' 카테고리의 다른 글
| [프로그래머스] 신규 아이디 추천 - Python (0) | 2021.04.03 |
|---|---|
| [프로그래머스] 3진법 뒤집기 - Python (0) | 2021.02.08 |
| 프로그래머스 캐시 (0) | 2020.12.01 |
| 프로그래머스 튜플 (0) | 2020.11.30 |
| 프로그래머스 n진수 게임 (0) | 2020.11.10 |