Kakao: 자네 키보드로 삽질해봤나?
주의❗. 읽기전에
- 이 문제의 풀이를 검색해 보니 정규표현식, DFS, 비트마스크로 푼 풀이들을 확인했습니다.
- 시험장에서 정규표현식을 사용하기에는 잘못 생각하면 예외가 발생하기 쉽기에 익숙하지 않은 이상 지향하는 편입니다. 또한, 재귀적 풀이도 좋아하는 편은 아닙니다.
- 저는 본 문제를 정규표현식과 재귀를 사용하지 않고 풀었습니다. 정해와 거리가 있을 수 있습니다.
🙅♂ 불량사용자 문제 확인
👀 입력값 관찰
user_id와 banned_id의 배열의 크기가 1 이상 8 이하라고 합니다. - 최악의 경우 8! = 40320이므로 안심하고 완전탐색으로 접근해도 됩니다.
- 카카오 코딩테스트는 특히 예외 처리를 주의 깊게 해야 합니다.
user_id = ["frodo", "fradi", "crodo", "abc123", "frodoc"]
banned_id = ["*rodo", "*rodo", "******"]
- 예시로 주어진
user_id와 banned_id가 위와과 같습니다.
('frodo', 'fradi', 'crodo')
('frodo', 'fradi', 'abc123')
('frodo', 'fradi', 'frodoc')
...
('frodoc', 'abc123', 'frodo')
('frodoc', 'abc123', 'fradi')
('frodoc', 'abc123', 'crodo')
- 순열로 나올 수 있는 유저의 경우 3가지를 골랐습니다.
banned_id = ['*rodo', '*rodo', '******']
Case 1. ('frodo', 'crodo', 'abc123')
Case 2. ('crodo', 'frodo', 'abc123')
- 유저 아이디의 경우의 수를 banned_id와 비교하면 예외 처리해야할 Case 1과 Case 2가 생깁니다.
- Case 1과 Case 2는 같은 경우의 수로 처리해주어야 합니다.
✏️ 문제 해결방법
✔️ STEP 1. 후보 유저 아이디 목록 생성
def solution(user_ids, banned_ids):
ans = list()
for candidate_users in permutations(user_ids, len(banned_ids)):
if check(banned_ids, candidate_users) is True:
# 중략 ...
return len(ans)
- 라인 4.
permutations을 이용하여 banned_ids와 매칭할 유저의 모든 조합의 수를 만듭니다.
- 라인 5.
check 함수에서 유저가 banned_ids와 매칭되는지 확인합니다.
- 👀 입력값 관찰에서 사용한 입력값으로 예를 들면
- banned_ids가 ["rodo", "rodo", "**"]에 ('frodo', 'fradi', 'crodo')가 매칭되는지, 하나씩 검사할 것입니다.
✔️ STEP 2. 불량 아이디 목록, 유저 아이디 목록이 일치하는지 확인
def check(banned_ids, candidate_users):
for i in range(len(banned_ids)):
if len(banned_ids[i]) != len(candidate_users[i]):
return False
if isMatchId(banned_ids[i], candidate_users[i]) is False:
return False
return True
- 라인 3. 유저의 아이디의 길이가 불량 사용자 아이디의 길이가 다르면 매칭될 일이 없습니다. 따라서 False를 리턴합니다.
- 라인 5.
isMatchId함수에서 각각 아이디가 일치하는지 확인합니다.
✔️ STEP 3. 불량 아이디, 유저 아이디 일치하는지 확인
def isMatchId(ban_id, user_id):
for i in range(len(ban_id)):
if ban_id[i] == '*': continue
elif ban_id[i] != user_id[i]:
return False
return True
- 글자를 하나씩 읽으면서 유저 아이디가 불량 아이디와 일치하는지 확인합니다.
✔️ STEP 4. 중복 유저 아이디 후보 제거
def solution(user_ids, banned_ids):
ans = list()
for candidate_users in permutations(user_ids, len(banned_ids)):
if check(banned_ids, candidate_users) is True:
candidate_users = set(candidate_users)
if candidate_users not in ans:
ans.append(candidate_users)
return len(ans)
- 다시 solution 함수로 돌아옵니다.
- 라인 6. 유저 아이디 목록이 불량 아이디 목록과 일치하면 set으로 변환합니다.
- 👀 입력값 관찰에서 확인한 것처럼 ('frodo', 'crodo', 'abc123')와 ('crodo', 'frodo', 'abc123')를 구분하기 위함입니다.
- ans에 불량 아이디에 매칭되는 유저 아이디 목록을 넣습니다. set으로 넣었기에 ('frodo', 'crodo', 'abc123')와 ('crodo', 'frodo', 'abc123')를 같은 경우의 수로 처리할 것입니다.
- ans의 크기가 정답이 됩니다.
⭕ 최종 풀이
from itertools import permutations
def isMatchId(ban_id, user_id):
for i in range(len(ban_id)):
if ban_id[i] == '*': continue
elif ban_id[i] != user_id[i]:
return False
return True
def check(banned_ids, candidate_users):
for i in range(len(banned_ids)):
if len(banned_ids[i]) != len(candidate_users[i]):
return False
if isMatchId(banned_ids[i], candidate_users[i]) is False:
return False
return True
def solution(user_ids, banned_ids):
ans = list()
for candidate_users in permutations(user_ids, len(banned_ids)):
if check(banned_ids, candidate_users) is True:
candidate_users = set(candidate_users)
if candidate_users not in ans:
ans.append(candidate_users)
return len(ans)
사족..
- 함수를 3개 사용한 이유는 flag 변수의 남발을 막기 위함입니다.
- 시험을 보면 생각했던 풀이가 오히려 코드가 더 길고 돌아가는 풀이일 수 있습니다. 일단 한번 그 풀이를 잡았다면 우선은 끝까지 풀어보는 것을 추천합니다. 생각보다 시험장에서 최적의 풀이가 생각나지 않을 때가 많거든요.