프로그래머스: 불량 사용자(JS, backtracking) feat. 현대캐피탈 2024 상반기 공개채용

알고리즘을 하도 오랜만에 풀었더니 백트래킹이라는 알고리즘을 까먹었어서 되새길겸 쓰는 글이다.

문제는 간단하다. 불량 사용자 배열의 원소들이 각각 가능한 경우의 수를 구하고 이 중 중복이 존재할 수 있고, 불량 사용자 배열의 길이 및 사용자 아이디 배열의 길이가 8이하로 매우 작으니 백트래킹을 이용해 가능한 모든 경우의 수를 구하면 된다.

 

백트래킹을 사용하는 이유는 매번 빈 배열을 dfs에 넣어야하기 때문이다. 현대 캐피탈 2024 상반기 공채 3번이 딱 이런 문제였는데 난 그때 백트래킹을 생각을 못해서 재귀함수의 depth가 0일때 재귀함수 안에서 빈 배열을 생성하여 그 배열에 원소를 넣고 재귀함수에 다시 prop으로 넣는 방식으로 풀었었다. 참고로 1번은 구현, 2번은 그래프탐색(BFS사용), 3번은 백트래킹, 4번은 DP였고 3솔이 합격 컷이였다.

 

다시 문제로 돌아와서 백트래킹의 핵심은 재귀를 호출할 조건을 제한하는 것과, 재귀를 통해 만들어진 집합이 순서만 다른 같은 집합일수있으니 정렬후 문자화하여 다시 집합에서 같은지 다른지 구별하는 것이다.

let list = new Set();
function solution(user_id, banned_id) {
    let sets = []
    banned_id.forEach((b,i)=>{
        let cash = new Set()
        user_id.forEach(u=>{
            if(isSame(u,b)){
                cash.add(u)
            }
        })
        sets.push(cash)
    })
    let c = new Set();
    dfs(sets, banned_id.length, 0, c)
    return list.size;
}

function isSame(user, banned){
    if(user.length !== banned.length){
        return false
    }
    else{
        judge = true
        banned.split('').forEach((b,i)=>{
            if(b !== '*' && b !== user[i]){  
                judge = false
            }
        })
        if(judge){
            return true
        }
        else{
            return false
        }

    }
}

function dfs(array, len ,n, cash){
    if(cash.size === len){
        list.add([...cash].sort().toString());
        return
    }
    if(n === len){
        return
    }
    array[n].forEach((v)=>{
        if(!cash.has(v)){
            cash.add(v)
            dfs(array, len, n+1, cash)
            cash.delete(v)
        }
        else{
            return
        }
    })
}