[Javascript/PGS] Lv.3 : 불량 사용자(2019 카카오 개발자 겨울 인턴십)

 

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

프로그래머스

---

프로그래머스 레벨 3.

2019 카카오 개발자 겨울 인턴십 기출 문제이다

소요시간 1시간 이상 ,,,

 

처음에 봤을땐 쉬워보였는데, 꽤 오래 삽질했다. 간단한 문제가 아니다......

하지만 원리만 이해한다면 금방 풀 수 있을듯!!

 

풀이 순서

 

1. 첫 시도 실패

=> 단순 문자열 비교인 줄 알고 삼중 반복문을 썼으나, 중복이 허용되지 않고 모든 경우의 수를 탐색해야 하는 조합 문제였음

 

2. 힌트 get

=> dfs로 풀어야 한다는 힌트를 얻었고.... 아무리 머리를 써도 왜 dfs를 써야하는건지 이해가 안됨

그래서 GPT 붙잡고 계속 삽질했다

 

힌트 내놔라~~~~~~~!!!!!

 

3. 이해 성공

=> banned_id[0]에 매칭되는 한 가지 경우를 찾았을 때, 그 다음 인덱스부터 다시 탐색을 해야하고

       한 가지 경우의 탐색이 끝나면 banned_id[0]에 매칭되는 다른 경우의 탐색도 진행하기에

        경우의 수를 찾기 위해 깊이우선 탐색을 진행하는 것!

=> 그리고 중복이 허용되지 않지만, Set은 배열을 비교할 때 순서가 다르다면 다른 요소로 인식함.

        따라서 Set으로 필터링할 때 ans_arr의 내부 요소를 정렬 후 문자열로 합쳐주었다.

 

 

나의 풀이

let answer = 0;
var ans_arr = [];

const isMatch=(ban, id)=>{
    if(!ban || !id) return false;
    if(ban.length===id.length){
        for(let i=0; i<ban.length; ++i){
            if(ban[i]=="*" || ban[i] === id[i]){
                continue;
            }
            else return false;
        }
        return true;
    }
    return false;
}

const dfs=(ban_list, users, ban_result)=>{
    if(ban_list.length === ban_result.length) {
        // console.log(ban_result)
        ans_arr.push(ban_result);
        return;
    }
    let ban = ban_list[ban_result.length];
    for(let i=0; i<users.length; ++i){
        if(isMatch(ban, users[i])){
            // console.log(ban, users[i]);
            dfs(ban_list, users.filter((_, idx) => idx !== i), 
                    [...ban_result, users[i]]);
        }
    }
}

function solution(user_id, banned_id) {
    let remain_users = [...user_id];
    let ban_list = [...banned_id];
    dfs(ban_list, remain_users, []);
    // console.log(ans_arr);
    answer = Array.from(new Set(ans_arr.map(x=>x.sort().join(',')))).length;
    return answer;
}