🔎 문제
🧩 구현과정 및 코드
개인 토글 영역에 구현 과정과 코드를 자유롭게 작성해주시면 됩니다.
사용할 데이터 구조와 풀이 방향성
적용할 알고리즘 혹은 메서드
수영
구현
- dfs
코드
function solution(user_id, banned_id) { const visitied = Array(user_id.length).fill(false); // 시행착오: .(한 문자)을 모를 때 \w(알파벳, 숫자, _ 중 한 문자)로 해봤는데 실패. const regex = banned_id.map(id => new RegExp(`^${id.replaceAll('*', '.')}$`)); // [ /^fr.d.$/, /^abc1..$/ ] const set = new Set(); const dfs = (idx, arr) => { if (idx === banned_id.length) { set.add(arr.sort().join(',')); } else { for (let i = 0; i < user_id.length; i++) { if (visitied[i]) { continue; } if (user_id[i].match(regex[idx])) { visitied[i] = true; dfs(idx + 1, [...arr, user_id[i]]); visitied[i] = false; } } } }; dfs(0, []); // {'abc123, frodo','abc123, fradi'} return set.size; }
정은
구현
- user_id를 banned_id 길이 만큼의 순열을 구해서 짝 리스트를 만든다
- 각 짝들과 banned_id가 모두 일치한다면, 해당 짝은 정답에 포함됨
코드
from itertools import permutations def isMatch(candidate, banned_id): # 문자마다 비교 for i in range(len(candidate)): if banned_id[i]=='*':continue # 불량 사용자의 문자가 *이 아니고 아이디가 다르면 False elif (banned_id[i] != candidate[i]): return False return True def check(candidate, banned_id): # 조합에 따른 유저 ID의 후보와 불량 사용자 아이디 각각을 비교 for i in range(len(banned_id)): # 불량 사용자와 유저의 아이디 길이가 다르면 false if len(candidate[i])!=len(banned_id[i]): return False # 길이가 같다면 해당 쌍을 비교 if isMatch(candidate[i], banned_id[i]) is False: return False return True def solution(user_id, banned_id): answer = [] for candidate in permutations(user_id, len(banned_id)): #banned_id 길이 만큼의 순열 if check(candidate, banned_id) is True: res=set(candidate) #answer에 중복되어 담지 않기 위해 모두 set형태로 담음 if res not in answer: answer.append(res) return len(answer)
종혁
구현
- 목록을 한 개씩 구한다고 생각
- 유저 한명씩 → 벤 아이디 전체에서 본인이 벤 될 수 있는 아이디를 찾기
- 한 아이디는 한개의 벤 아이디만 가질 수 있음
- 유저 한명씩 → 전체 벤 목록을 조사하면서 본인 아이디가 벤 될 수 있다면 해당 벤 아이디는 사용된 걸로 간주하고 다음 유저로 넘어가기
- dfs를 사용하면 알아서 다시 돌아옴(?)
user ["frodo", "fradi", "crodo", "abc123", "frodoc"] ban ["fr*d*", "abc1**"] 'frodo' -> "fr*d*"로 인해서 벤 됨 'fradi' -> "fr*d*"로 인해서 벤 될 수 있지만 앞에서 사용함 "abc123" -> "abc1**"로 인해 벤 되면서 리턴됨 dfs에 의해서 'frodo'가 "fr*d*"로 인해 벤 되지 않은 상태로 돌아감 'fradi' -> "fr*d*"로 인해서 벤 됨 "abc1**" -> "abc123"로 인해 벤 되면서 리턴됨 [frodo,abc123] [fradi,abc123]
코드
function solution(users, banned) { let num = 0 banned.forEach(ban => { for(const user of users){ if(user.length !==ban.length){continue} let isBan = true for(let i=0;i<user.length;i++){ if(ban[i] === '*'){continue} if(ban[i] !== user[i]){ isBan = false break} } if(isBan){ num ++ break } } })//벤 목록에 들어와야 할 아이디의 갯수 const result = [] const dfs = (i,isUsed,list) => { if(isUsed.every(v => v === 1)){ result.push(String(list.sort())) return } if(i>=users.length){ if(list.length === num){//유저를 다 탐색했을 경우-> list에 벤 되어야하는 모든 유저가 있어함 result.push(String(list.sort())) } return } const user = users[i] for(let j=0;j<banned.length;j++){//user가 벤 목록에 있는지 벤 목록 한명씩과 비교 let isBanned = true if(isUsed[j] || banned[j].length !== user.length){continue} for(let k=0;k<user.length;k++){//문자 하나씩 비교 if(banned[j][k] === '*'){continue} if(banned[j][k] !== user[k]){ isBanned = false // 한글자라도 안맞으면 종료 break} } if(isBanned){//다 맞는경우에만 ban 가능 isUsed[j] = 1 dfs(i+1,[...isUsed],[...list,user]) isUsed[j] = 0} } dfs(i+1,isUsed,list) } dfs(0,Array(banned.length).fill(0),[]) //순서 중요 X - 원소가 중복되진 않는지 return new Set(result).size }
재웅
구현
- 불량 사용자 필터링
- 정규식?
*의 인덱스를 따와서user_id와 대조?- 최적화는? → 입력 배열의 크기가 그리 크지 않음
const bannedList = new Array(); banned_id.forEach((bid) => { let pattern = new RegExp(bid.replaceAll('*', '.*')); let dstList = new Array(); user_id.forEach((uid) => { if (pattern.test(uid) && uid.length === bid.length) { dstList.push(uid); } }); bannedList.push(dstList); }); >> [ [ 'frodo', 'crodo' ], [ 'frodo', 'crodo' ], [ 'abc123', 'frodoc' ] ] >> [ [ 'frodo', 'fradi' ], [ 'frodo', 'crodo' ], [ 'abc123', 'frodoc' ], [ 'abc123', 'frodoc' ] ]
- 조합으로 경우의 수 추출
코드
function solution(user_id, banned_id) { // 정규식을 이용해 필터링 const bannedList = new Array(); banned_id.forEach((bid) => { let pattern = new RegExp(bid.replaceAll('*', '.*')); let dstList = new Array(); user_id.forEach((uid) => { if (pattern.test(uid) && uid.length === bid.length) { dstList.push(uid); } }); bannedList.push(dstList); }); // 경우의 수 추출 const results = new Set(); function dfs(idx, selected) { if (idx === bannedList.length) { results.add(selected.sort().join(',')); return; } for (let i = 0; i < bannedList[idx].length; i++) { if (!selected.includes(bannedList[idx][i])) { dfs(idx + 1, [...selected, bannedList[idx][i]]); } } } dfs(0, []); return results.size; }
→ 테케 3, 7 틀리는데, 이유를…
- 정규식 문제..
let pattern = new RegExp("^" + bid.replaceAll('*', '.*') + "$");
✏️ 후기
문제를 풀고 느낀 점, 막혔던 부분 혹은 개선 사항 등을 자유롭게 작성해주시면 됩니다.
수영
- dfs를 떠올리지 못해서 더 어렵게 푼 것 같다
- 정규표현식을 알고 있으면 문자열을 다루기 편하다는 생각이 들었다. 어려운 내용은 나오지 않는 것 같아서 내용을 다시 봐야 겠다.
정은
- 정규식을 쓰려다가 실패..ㅎ 정규식으로 다시 풀어봐야 할 것 같다
종혁
- 관점을 다르게 보면 생각보다 쉬울것 같기도..
재웅