[JS] 불량 사용자

정규표현식과 set , dfs 를 활용하여 해결한 문제였다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/64064

프로그래머스

 

 

정규표현식은 불량 사용자인지 아닌지를 가져오기 위해서 사용했는데 굳이 정규표현식이 아닌 반복문을 활용해서 풀었어도 상관은 없을 문제인듯 하다.

 

1. 정규표현식으로 banned_id마다 가능한 아이디의 조합을 가져오기

 

EX) TEST CASE 3

[ [ 'frodo', 'fradi' ], [ 'frodo', 'crodo' ], [ 'abc123', 'frodoc' ], [ 'abc123', 'frodoc' ] ]

 

2. dfs를 활용하여 만들 수 있는 조합 만들기

한번 사용한 이름은 사용할 수 없으므로 객체를 하나 만들어서 중복이 안들어가는 조합들을 만들었다.

 

3. 중복 제거

set을 활용해서 만들어둔 조합 중 순서만 다른것들을 삭제해주었다.

-> 배열에 이름조합들을 넣을때 문자가 아닌 숫자로 넣어주었다.

-> user_id의 순서대로 불량사용자로 뽑힌 사용자를 1로 바꿔주는식

 

EX ) TEST CASE 3

 

user_id -> ["frodo", "fradi", "crodo", "abc123", "frodoc"] -> 00000이라 생각

 

'frodo','crodo','abc123','frodoc' -> 10111

'frodo','crodo','frodoc','abc123' -> 10111

 

위와 같은 방식으로 중복된 값들을 제거해주었다.

 

 

 

 

function solution(user_id, banned_id) {
    const bannedIdList = banned_id.map(v => {
        const reg = new RegExp('^'+[...v].map(v => v==='*' ? '.' : v).join('')+'$')
        return user_id.filter(v => reg.test(v))
    })
    
    let ret = []
    const obj = {}
    for (const user of user_id){
        obj[user] = false
    }
    
    const dfs = (depth) => {
        if (depth === banned_id.length){
            const tmp = Array(user_id.length).fill(0)
            for (const [user,val] of Object.entries(obj)){
                if(val) tmp[user_id.indexOf(user)] = 1
            }
            ret.push(tmp.join(''))
            return
        }
        
        for (const id of bannedIdList[depth]){
            if (obj[id]) continue
            obj[id] = true
            dfs(depth+1)
            obj[id] = false
        }
    }
    
    dfs(0)
    return new Set(ret).size
}